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

1. 문제

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

 

2. 접근 방식

매개 변수로 전해지는 n의 값을 이진수로 변환을 하고, n값부터 1씩 증가시켜서 완전 탐색을 하면 시간초과가 날 것이라 생각했다. 다음 큰 수를 찾는 방식에 규칙이 존재할 거라 판단했지만 규칙을 발견하기엔 너무 복잡했다. 결국 원점으로 돌아와 n값부터 1씩 증가시키며 완전탐색을 하기로 했다. 

 

처음 생각과는 달리 시간 초과가 나질 않았다. 이유는 최대 값인 1,000,000을 2로 나눠서 0이되는 연산 횟수는 20번, 1부터 1,000,000까지 탐색을 한다해도 1초 이하의 시간으로 값을 구할 수 있기 때문이다. 문제를 꼼꼼히 읽어보며 판단을 해야한다.

 

3. 구현

class Solution {
    public int solution(int n) {
        int answer = n;
        StringBuilder sb = new StringBuilder();
        
        while (n != 0) {
            int temp = n%2;
            sb.append(temp);
            n /= 2;
        }
        
        int count = 0;
        for (int i=0; i<sb.length(); i++) {
            if (sb.charAt(i) == '1') {
                count++;
            }
        }
    
        return findNextBigNum(answer, count);
    }
    
    public int findNextBigNum(int n, int count) {
        int temp = 0;

        for (int i=1; i<1000000-n; i++) {
            int tempCnt = 0;
            n++;
            temp = n;
            while (temp != 0) {
                if (temp%2 == 1) {
                    tempCnt++;
                }
                temp /= 2;
            }
            if (tempCnt == count) {
                break;
            }
        }
        
        return n;
    }
}

 

4. 정리

Integer클래스의 bitCount() 메소드로 해결하는 방법이 있다.

public int nextBigNumber(int n){
                 int a = Integer.bitCount(n);
          while (Integer.bitCount(++n) != a) {}
          return n;
    }

이외에도 toBinaryString()을 사용할 수도 있다. 이진수 변환을 여러가지 방법으로 할 수 있다는 걸 알게된 좋은 문제였다.