[2진수 변환] 프로그래머스 level2 다음 큰 숫자 c++ 풀이

프로그래머스 다음 큰 숫자 c++ 풀이

• Level 2
• 연습문제
• 다음 큰 숫자
  
  
  

문제 정리

1. 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음고 같다.
   ```
2. n의 다음 큰 숫자는 n보다 큰 자연수
3. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같다.
4. n의 다음 큰 숫자는 조건 1,2를 만족하는 수 중 가장 작은 수
5. n은 1,000,000 이하의 자연수이다.

   <br><br>
   

문제 풀이

1. n보다 큰 숫자부터 2진수로 변환하여 1의 개수를 세본다.
2. 개수를 세서 n의 1의 개수와 같다면 조건 1을 만족하고, 자동으로 조건 2도 만족하게 된다.
3. 1의 개수는 이진수로 변환하는 로을 그대로 적용하면 된다. 2로 나눠서 2로 나눠 떨어지지 않는다면 1이 하나 있다는 뜻이다.
4. 이를 n이 2나 1이 될때까지 반복한다. 마지막 맨 왼쪽 비트는 항상 1이므로 이때도 1의 개수를 세준다.
5. 이 조건을 만족하는 수 n을 출력하면 된다
   
   
   

프로그래머스 다음 큰 숫자 c++ 코드

#include <iostream>
using namespace std;

int n;

int countOne(int n) {
    int cnt = 0;

    while (1) {
        if (n % 2 != 0)
            cnt++;
        n /= 2;
        if (n == 2 || n == 1) {
            cnt++;
            break;
        }
    }

    return cnt;
}

int solution(int n) {
    int cnt = countOne(n);

    n++;
    while (1) {
        if (cnt == countOne(n)) {
            return n;
        }
        n++;
    }
}

int main() {
    // IO 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    cout << solution(n) << "\n";

    return 0;
}