[Lv2] 다음 큰 숫자

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

자연수 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)입니다.

 

---

 

현재 숫자 n보다 크면서, 2진법으로 표현했을 때 1의 수가 같아야 합니다. 그런 최소 숫자를 찾으면 끝입니다.

 

2진법 변환은 2로 소인수 분해가 반복되면 됩니다. 2로 나눌 때는 나머지가 0, 1 둘 뿐입니다.

 

141을 2로 나누면 70과 1,

70을 2로 나누면 35와 0,

35를 2로 나누면 17과 1,

17을 2로 나누면 8과 1,

8을 2로 나누면 4와 0,

4를 2로 나누면 2와 0,

2를 2로 나누면 1과 0.

 

마지막으로 2를 나눌 수는 2이상입니다. 즉, 나눌 수가 1이 될 때 까지만 나눕니다.

 

마지막 나눌 수(1)를 필두로하여 나머지를 역으로 뒤로 세웁니다. 즉, 10001101.

 

나머지를 순서대로 저장했다가 역순으로 펼치든, 앞에 붙여나가면서 역으로 저장했든..

그 앞에 1만 붙이면 됩니다.

 

실제로 아래 코드에서는 기본적으로 제공하는 기능을 이용합니다.

 

public int solution(int n) {
    String origin_bi = Integer.toBinaryString(n);
    char[] origin_arr = origin_bi.toCharArray();
    int count = 0;
    for(int i=0;i<origin_arr.length;i++) {
        if(origin_arr[i]=='1') count++;
    }
    int next = n;
    while(true) {
        next++;
        String next_bi = Integer.toBinaryString(next);
        char[] next_arr = next_bi.toCharArray();
        int cal = 0;
        for(int i=0;i<next_arr.length;i++) {
            if(cal>count) break;
            if(next_arr[i]=='1') cal++;
        }
        if(cal==count) break;
    }
    return next;
}

 

Integer.toBinaryString()으로 1과0으로 표현되는 문자열 생성 후, 1의 숫자를 셉니다.

 

숫자를 1씩 키워가면서 1의 갯수가 동일한 수에서 바로 멈추고 반환.