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

문제

다음 큰 숫자 : 문제 링크

문제 분석

• 자연수 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을 2진수로 변환했을때 1의 갯수를 저장할 정수형 변수 one을 0으로, n값을 저장할 정수형 변수 n_c를 초기화. while loop의 조건식을 n_c로 설정하여 n_c가 자연수인동안 반복하고, if문을 통해 n_c를 2로 나눈 나머지가 1일경우 one을 1씩 늘리고, n_c에 2로 나눈 몫을 저장. for loop의 초기화식을 i = n + 1로 설정하여 조건1을 만족하고, i를 2진수로 변환했을때 1의 갯수를 저장할 정수형 변수 count를 0으로, i값을 저장할 정수형 변수 tmp를 초기화. 이전과 마찬가지로 while loop의 조건식을 tmp로 설정하여 tmp가 자연수인동안 반복하고, if문을 통해 tmp를 2로 나눈 나머지가 1일경우 count를 1씩 늘리고, tmp에 2로 나눈 몫을 저장. loop 탈출 후, if문을 통해 one과 count가 같다면 조건2를 만족하므로 i를 return

풀이

using namespace std;

int solution(int n) {
    int one = 0, n_c = n;
    
    while(n_c) {
        if(n_c % 2 == 1) one++;
        n_c /= 2;
    }
    for(int i = n + 1;; ++i) {
        int count = 0, tmp = i;
        
        while(tmp) {
            if(tmp % 2 == 1) count++;
            tmp /= 2;
        }
        if(one == count) return i;
    }
}