[프로그래머스] 다음 큰 숫자

📌다음 큰 숫자

자연수 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

📌사용 언어 : JAVA

📌solution_01

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

        String binaryN = Integer.toBinaryString(n);
        String[] arrN = binaryN.split("");
        while(true){
            n++;
            int cntN = 0;
            int cntA = 0;
            String binaryA = Integer.toBinaryString(n);
            String[] arrA = binaryA.split("");
            for(int i = 0; i < binaryN.length(); i++){
                if(arrN[i].equals("1")){
                    cntN++;
                }
            }
            for(int i = 0; i < binaryA.length(); i++){
                if(arrA[i].equals("1")){
                    cntA++;
                }
            }
            if(cntN == cntA){
                answer = n;
                break;
            }
        }

        return answer;
    }
}

😦문제 발생

막연히 입력받은 n을 Integer.toBinaryString(n)으로 이진수로 변환한 다음 이걸 하나하나 쪼개서 배열에 담은 후 1의 갯수를 세서 비교하려고 했다. 말만 들어도 번거롭다...하여튼 코드를 작성하고 실행했더니 정확성은 만점이었는데 효율성이 빵점이다... 찾아보니 bitCount라는 메소드가 있더라. n을 이진수로 변환한 수의 1의 갯수를 세어 int값으로 반환하는 메소드라는데..이걸 사용해 보기로 했다.

📌solution_02

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

        int cntN = Integer.bitCount(n);

        int cntA = 0;
        
        while(true){
            n++;
            cntA = Integer.bitCount(n);
            if(cntN == cntA){
                answer = n;
                break;
            }
        }

        return answer;
    }
}

😎풀이

훨씬 간단해졌다. 변수 cntN에 bitCount메소드를 사용해 n의 이진변환한 수의 1의 갯수를 담고, while문 안에서 n을 1씩 증가시킨다. 그리고 증가시킨 n의 이진변환한 수의 1의 갯수를 cntA에 담아준다. cntA와 cntN이 같다면 answer에 n을 담아주고 while문을 빠져나온다.