[프로그래머스] Lv.2 2개 이하로 다른 비트 문제 해결 과정(Java)

문제 링크

 https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

 

 

해결 과정

 문제를 읽었을 때부터 어떻게 풀어야 할지 감도 안 와서 일단 무작정 이진수를 써 내려갔다. 그러다 보니 이진수의 마지막 2자리의 형태에 따라서 반환하는 값의 형태가 비슷하다는 것을 인지했다. 그래서 일단 2가지의 경우로 반환했다.

• 이진수의 마지막이 "11"인 경우(== 10진수 형태의 정수를 4로 나눈 나머지가 3인 경우)
• 그 외의 경우(== 10진수 형태의 정수를 4로 나눈 나머지가 0, 1, 2일 경우)

 2번째의 경우에는 원래 값에서 1만 더해주면 된다. 근데 진짜 문제는 첫 번째였다. 이 부분에서 어떻게 처리해야 할지 아무리 생각해 봐도 떠오르지 않았다. 나는 15(1111), 19(10011) 2개의 숫자를 유심히 살펴보았다.

 

 우선, 두 숫자 모두 4로 나눈 나머지가 3이다. 그리고 내가 직접 찾은 값에 의하면 15의 함숫값은 23, 19의 함숫값은 21이었다. 

이해를 돕기 위한 사진

 이진수를 유심히 보니, 주어진 수를 4로 나누었을 때 나머지가 3이면, 해당 수를 2로 나누어 같은 과정을 반복하고. 그렇지 않으면, 주어진 수에서 1을 더하여 반환하는 규칙을 발견했다. 또한 나머지가 3일 때 원래 주어진 수를 정확하게 복구하기 위해서 2로 나눈 나머지 값도 같이 더했다.(이 부분은 제가 아직 매끄럽게 설명하지 못해서 나중에 깔끔하게 정리할 수 있으면 하겠습니다.)

 

 결국 나는 이 문제를 재귀로 해결했다.

수행 결과

 

 원래는 xor연산자를 사용하여 해결해보고 싶었지만, 이후에 처리 로직이 떠오르지 않아서 결국은 포기했다. 그런데 다른 분의 풀이를 보니 비트 시프트 연산자로 해결한 풀이가 있었다. 오랜만에 보는 비트 시프트 연산자라 무슨 연산자들이 있었는지 기억이 나지 않았는데 이번 기회로 정리해 봐야겠다. 그리고 이 풀이 방법이 내가 해결한 방법보다 더 간단하고 수행속도도 빨랐다.

비트 시프트 연산자

• >> n : 부호를 유지시키면서 비트를 오른쪽으로 n번 이동시킴
• << n : 부호를 유지시키면서 비트를 왼쪽으로 n번 이동시킴
• >>> n : 부호와 상관없이 가장 왼쪽 비트를 0으로 채우며 오른쪽으로 n번 이동시킴
• <<< n: 부호와 상관없이 가장 오른쪽 비트를 0으로 채우며 왼쪽으로 n번 이동시킴

 

 

전체 코드

//나의 풀이(재귀 사용)
class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for(int i = 0; i < numbers.length; i++) {
            answer[i] = function(numbers[i]);
        }
        return answer;
    }
    
    private long function(long number) {
        //11이 아니면 주어진 수에서 1을 더하여 반환
        //주어진 수의 이진수의 마지막 2자리가 11이면 2로 나누어서 재귀적으로 수행
        //원래 주어진 수를 복원하기 위해서 2로 나눈 나머지값도 더해준다.
        return number % 4 == 3 ? 2*function(number/2) + number%2 : number+1;
    }
}

 

 

정리 및 회고

• 비트 시프트 연산자를 사용할 일이 많지 않았어서 까먹고 있었는데, 이 문제를 오랫동안 고민하다가 발견한 부분이라 그래도 기억에 오래 남을 듯하다.
• 문제 푸는 시간이 오래 걸리긴 하지만 이리저리 생각해 보는 과정이 꽤 도움이 되는 것 같음
• 비트 연산자로 해결하는 방식은 당장 이해하기 쉽지 않은 것 같다. 무슨 의미인지 찬찬히 살펴봐야겠다.