[PROGRAMMERS] Level 2 두개 이하로 다른 비트 (이진탐색, JAVA)

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

프로그래머스

시간 제한이 없었다면 이 문제는 단순 구현으로 엄청 쉬운 문제지만, 시간 제한이 있어 규칙성을 찾는 재미있는 문제이다. 문제를 소개하고 JAVA로 풀이를 소개하고자 한다.

 

🎁 문제

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수비트다른 비트의 개수

2	000...0010
3	000...0011	1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수비트다른 비트의 개수

7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

---

입출력 예

[2,7]

[3,11]

 

📢 풀이

처음에는 비트 관련 문제라 비트 연산을 사용해야하나? 라는 걱정을 했지만 비트 연산자를 사용하지 않고 재미있는 규칙으로 풀어나갈 수 있다.

 

해당 규칙은 짝수와 홀수일 때 다르다.

1. 짝수

예를 들어 2를 생각해보자. 2의 이진수는 10이다. 다음 숫자인 3의 이진수는 11이다. 서로 다른 비트는 한 개로 f(2)=3이 된다.

이번에는 4를 생각해보자. 4의 이진수는 100이다. 다음 숫자인 5의 이진수는 101이다. 서로 다른 비트는 한 개로 f(4)=5가 된다. 설마.. 단순하게 +1은 아니겠지..? 라는 마음으로 28을 진행해보자!

28의 이진수는 11100 이다. 다음 숫자인 29의 이진수는 11101이다. 서로 다른 비트는 한 개로 f(28)=29가 된다. 

즉, 짝수의 규칙은 +1만 해주면 정답이 된다. 

 

2. 홀수

예를 들어 5를 생각해보자. 5의 이진수는 101이다. 다음 수인 6은 110으로 서로 다른 비트는 두 개가된다. 그렇다면 f(5)=6이 된다.

이번에는 11을 생각해보자. 11의 이진수는 1011이다. 다음 수인 12는 1100으로 서로 다른 비트가 3 개가된다. 그 다음 수인 13은 1101로 서로 다른 비트가 두 개가된다. 그러므로 f(11)=13이 된다.

이걸로는 규칙을 알 수 없다. 마지막으로 21의 이진수는 10101이다. 다음 수인 22는 10110으로 서로 다른 비트가 두 개가된다. 그러므로 f(21)=22가 된다.

 

이 때까지 나온 이진수에 주목해보자.

101     -> 110

1011   -> 1101

10101 -> 10110

 

규칙을 살펴보면 뒤에서 처음 발견한 0과 1의 자릿수를 변경하고 있다.. OMG😱

그렇다면 문제의 7을 해당 공식을 통해 답을 추론해보자. 7의 이진수는 111이다.

이 경우에는 0이 없으므로 강제로 앞에 0을 하나 추가해준다. 그러면 이진수는 0111이 된다.

그리고 뒤에서부터 0을 발견하고 있다면 바로 앞자리인 1과 자리를 변경해준다. 그러면 1011이 될 것이다.

1011 = 11로 문제의 정답과 동일하다. 

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for(int i=0; i<numbers.length; i++){
            if(numbers[i]%2==0) answer[i]=numbers[i]+1;
            else{
                String t=Long.toBinaryString(numbers[i]);
                if(t.indexOf("0")==-1) t="0"+t;
                char[] cArr=t.toCharArray();
                for(int j=cArr.length-1; j>0; j--){
                    if(cArr[j]=='1' && cArr[j-1]=='0'){
                        char temp=cArr[j];
                        cArr[j]=cArr[j-1];
                        cArr[j-1]=temp;
                        break;
                    }
                }
                t=String.valueOf(cArr);
                long ans=0;
                for(int j=0; j<t.length(); j++){
                    if(t.charAt(j)=='1')
                        ans+=Math.pow(2,t.length()-1-j);
                }
                answer[i]=ans;
            }
        }
        return answer;
    }
}

 

결과는 ....

정답을 맞췄을 때 바로 찍지못해서 점수가 출력이 안되었는데 해당 문제로 5점을 얻었다. 5점을 얻은 이유는 시간 측면에서 효율적으로 코드를 구성했기 때문이다.

 

📢 결론

C++이 익숙해서 계속 사용했는데 이제 JAVA로 이동하려고 한다. JAVA가 좀 더 간편한 라이브러리가 많다. 아직 적응을 못해서 사용하기에는 불편한 측면도 많다 ㅠㅠ... 개인적인 느낌으로 JAVA는 C++, Python 중간 성격인듯..