다음 큰 수

어떤 수 N(1≤N≤1,000,000) 이 주어졌을 때, N의 다음 큰 숫자는 다음과 같습니다.

• N의 다음 큰 숫자는 N을 2진수로 바꾸었을 때의 1의 개수와 같은 개수로 이루어진 수입니다.
• 1번째 조건을 만족하는 숫자들 중 N보다 큰 수 중에서 가장 작은 숫자를 찾아야 합니다.

예를 들어, 78을 2진수로 바꾸면 1001110 이며, 78의 다음 큰 숫자는 83으로 2진수는 1010011 입니다.
N이 주어질 때, N의 다음 큰 숫자를 찾는 nextBigNumber 함수를 완성하세요.

다음 이진수 1의 개수가 같은 수가 logn 자리 내에서 계산되기 때문에 범위가 100만까지인 수는 아무리 길어도 19자리를 넘지 않는다. 그래서 차례로 반복문을 돌려서 계산해도 될 것이라고 생각했다. 조건만 제대로 체크해주면 큰 어려움 없이 풀리는 문제였다.

class TryHelloWorld {
    public int nextBigNumber(int n) {
        int answer = 0;
        String num = Integer.toBinaryString(n);
        int count = 0;
 
        for (int i = 0; i < num.length(); i++) {
            if (num.charAt(i) == '1') {
                count++;
            }
        }
 
        while (answer == 0) {
            int tCount = 0;
            String tNum = Integer.toBinaryString(++n);
            for (int i = 0; i < tNum.length(); i++) {
                if (tNum.charAt(i) == '1') {
                    tCount++;
                }
            }
            if(tCount == count) {
                answer = n;
            }
        }
        return answer;
    }
 
    public static void main(String[] args) {
        TryHelloWorld test = new TryHelloWorld();
        int n = 78;
        System.out.println(test.nextBigNumber(n));
    }
}