[프로그래머스] 다음 큰 숫자(Java 자바)

https://programmers.co.kr/learn/courses/30/lessons/12911

코딩테스트 연습 - 다음 큰 숫자

문제 설명

자연수 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
문제 예시와 같습니다.
입출력 예#2
15(1111)의 다음 큰 숫자는 23(10111)입니다.

---

Solution 1

 

처음에는 해당 숫자를 이진수로 바꾸고 1을 카운트하여 저장하였다. 

이후에 숫자를 1씩 더해가면서 이진수로 바꾸고 1을 카운트 하는 것을 반복하면서 처음 숫자보다 크고 1의 수가 같은 숫자를 찾아 갔다.

 

하지만 이렇게 하면 효율성이 떨어지게 된다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        String now = binary(n);
        int nowCount = 0;
        
        for(int i = 0; i < now.length(); i++){
            if(now.charAt(i) == '1'){
                nowCount++;
            }
        }
        System.out.println(nowCount);
        
        while(true){
            n++;
            int nextCount = 0;
            
            String next = binary(n);
            
            for(int i = 0; i < next.length(); i++){
                if(next.charAt(i) == '1'){
                    nextCount++;
                }
            }
            
            if(nowCount == nextCount){
                break;
            }
        }
        
        return n;
    }
    
    public String binary(int n){
        StringBuilder sb = new StringBuilder();
        while(n > 0){
            sb.append(n % 2);
            n /= 2;
        }
        sb.reverse();
        
        return sb.toString();
    }
}

 

 

Solution2

 

1을 효율적으로 찾는 방법을 찾다보니 Integer 클래스에 bitCount라는 메소드를 알게 되었다.

    public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }

확실히 반복문을 돌면서 1을 찾는 것 보다 효율적이다. 

이 메소드를 사용하여 리팩토링을 하였다.

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        int nowCount = Integer.bitCount(n);

        while(true){
            n++;
            int nextCount = Integer.bitCount(n);

            if(nowCount == nextCount){
                break;
            }
        }

        answer = n;

        return answer;
    }
}

 

핵심 코드, 푸는법:

Integer.bitCount();