프로그래머스 Lv2 다음 큰 숫자

문제 설명

자연수 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 이하의 자연수 입니다.

---

입출력 예

n	result
78	83
15	23

입출력 예 설명

입출력 예#1문제 예시와 같습니다.입출력 예#215(1111)의 다음 큰 숫자는 23(10111)입니다.

---

나의 풀이

이전에 풀었던 이진 변환 문제와 흐름이 비슷해서 비교적 쉬웠다고 생각한다.

우선 저번과 마찬가지로 Integer.toBinaryString을 통해 이진 변환과 동시에 0을 제거하고 그 길이를 비교하는 방법으로 진행하였다.

코드는 다음과 같다

class Solution {
    public int solution(int n) {
        int answer = 0;

        String stan = Integer.toBinaryString(n).replaceAll("0", "");

        int tmp = n;
        while (true) {
            tmp++;
            String str = Integer.toBinaryString(tmp).replaceAll("0", "");
            if (stan.length() == str.length()) {
                answer = tmp;
                break;
            }
        }
        return answer;
    }
}

모든 테스트 케이스를 통과할 수 있었지만, 이번 문제 역시 효율성 테스트에서 막히게 되었다. 범위가 1,000,000 이하의 자연수이기 때문에 보다 수행 속도가 빠른 코드를 작성할 필요가 생겼다.

그렇게 고민하던 중 Integer.bitCount()를 찾게 되었는데, 이 함수는 주어진 정수를 이진으로 변환 후 true bit의 개수를 반환해주는 함수이다. 우리가 구하려는 것과 완전히 일치하는 것이다!

이를 통한 풀이는 다음과 같다

class Solution {
    public int solution(int n) {
        int answer = 0;

        int target = Integer.bitCount(n);

        int tmp = n;

        while (true) {
            tmp++;
            int cur = Integer.bitCount(tmp);
            if (target == cur) {
                answer = tmp;
                break;
            }
        }
        return answer;
    }
}