# 프로그래머스 : 다음 큰 숫자 (Level 3)

[문제]

어떤 수 N(1≤N≤1,000,000) 이 주어졌을 때, N의 다음 큰 숫자는 다음과 같습니다.

• N의 다음 큰 숫자는 N을 2진수로 바꾸었을 때의 1의 개수와 같은 개수로 이루어진 수입니다.
• 1번째 조건을 만족하는 숫자들 중 N보다 큰 수 중에서 가장 작은 숫자를 찾아야 합니다.

예를 들어, 78을 2진수로 바꾸면 1001110 이며, 
78의 다음 큰 숫자는 83으로 2진수는 1010011 입니다.

N이 주어질 때, N의 다음 큰 숫자를 찾는 nextBigNumber 함수를 완성하세요.

[풀이]

처음 문제를 접근할 때, 

1. 주어진 수를 2진수로 바꿔주고
2. 2진수로 바뀐 수의 전체 길이와 1의 갯수를 각각 세어주고
3. 주어진 수부터 전체 길이에서 1의 길이를 최대로 갖는 수까지 범위를 지정하고 검색

의 방식으로 '무식하게' 접근하였는데. 지금 생각하면 정말 바보같음

다시 알고리즘을 생각하였을 때는 다음과 같았다.

1. 주어진 수를 2진수로 바꾸었을 때 1의 갯수를 세어주고.
2. 주어진 수부터 1씩 증가할 때, 증가된 수가 2진수로 바뀌었을 때 1의 갯수가 동일한 경우 = 답

이렇게 간단한 알고리즘이었다.

무튼 뻘짓(!)을 한 덕분에 10진수가 입력되었을 때 2진수 스트링 형으로 바꿔주는 함수를 만들어보았다.

string tentotwo(int num) {

    int result = 0;

    for(int i=1; num>0; i*=10) {

        int binary = num%2;

        result += binary*i;

        num /= 2;

    }

    return to_string(result);
}

실제 알고리즘으로 구현한 결과는 다음과 같다.

int countone(int num) {

    int count = 0;

    for(int i=1; num>0; i*10) {

        if(num%2 ==1) count++;

        num /= 2;

    }

    return count;
}

int nextBigNumber(int n)

{

    int answer= 0;

    int count = countone(n);

    

    for(int i=n+1; ; i++) {

        if(countone(i) == count) {

            answer = i;

            break;

        }

    }

    return answer;

}

countone 함수는 주어진 10진수를 2진수로 바꾸었을 때 1의 갯수를 출력해주는 역할을 하고,

nextBigNumber는 주어진 수+1 부터 계속 증가해가면서, 2진수로 변환된 수의 1의 갯수가 동일하면 곧바로 반환시킨다.

사실 어려운 문제는 아니었는데, 처음 접근을 괜히 너무 어렵게 하는 바람에 조금 애먹은 문제;;