[TIL] 프로그래머스 lv.2 다음 큰 숫자 (비트연산자)

문제

문제 설명
자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.
조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.
자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

제한 사항
n은 1,000,000 이하의 자연수 입니다.

---

나의 풀이

풀이 로직

1. String을 매개변수로 받아 1의 개수를 세어 int로 return하는 메서드 countOneOfStr을 만든다.
2. int n을 Integer.toBinaryString(n)으로 2진법으로 바꿔 준다.
3. n++를 하면서 countOneOfStr로 1의 개수를 세어 준 후, n의 1의 개수와 같으면 return한다.

풀이 코드

public int solution(int n) {
    String binaryN = Integer.toBinaryString(n);
    int countOneOfN = countOneOfStr(binaryN);
    int temp = 0;
    while (temp != countOneOfN) {
        n++;
        temp = countOneOfStr(Integer.toBinaryString(n));
    }
    return n;
}

public int countOneOfStr(String str) {
    int count = 0;
    for (int i = 0; i < str.length(); i++) {
        if (str.charAt(i) == '1') {
            count++;
        }
    }
    return count;
}

---

다른 사람의 풀이

풀이 코드

public int solution(int n) {
    int postPattern = n & -n;
    int smallPattern = ((n ^ (n + postPattern)) / postPattern) >> 2;
    return n + postPattern | smallPattern;
}

코드 해석

원래 다른 사람의 풀이는 어느 정도 보면 이해가 가면서 와 이렇게 풀었구나 하는데

이번 풀이는 ??? 뭐지? 왜 이렇게 푼거지 정말 한참 고민했다. 분석을 하고 나니까 아 그래서 다음 큰 숫자가 나오는거구나 싶어도 나보고 비슷하게 다시 풀어봐~ 하면 생각해 낼 수 있을지 잘 모르겠다. 그래도 모르는 것을 분석해보고 이해했다는 것 만으로 일단 만족..!