다음 큰 숫자

들어가는 말

주어진 숫자와 2진수의 1이 같은 최소값을 찾는 문제이다. 문제의 관건은 어떻게 이진수의 1의 개수를 찾느냐이다. 2로 나누면서 나머지가 1인 경우를 셀 수도 있지만, 나는 비트 연산자로 개수를 셌다. n과 n-1을 and로 취하면 맨 마지막 비트가 사라진다는 특성을 이용한 것이다(기본 아이디어는 인터넷 검색을 참고했다). 때문에 n을 계속 -1하여 and를 취하며 n이 0이 될 때까지 해준다.
빨리 풀 수 있을 거라 생각했는데, 예상보다 시간이 걸렸다. if문까지는 잘 써 줬으나 else를 쓰지 않은 것이 문제였다. else에다가 answer++를 해줘야 하는데, 그냥 answer++를 했더니 무한 루프로 돌아가서 애를 먹었다. 차분히 생각하고 풀면 될 것을... 허둥지둥하다가 시간을 꽤 날린 느낌이다.
그럼에도 90%는 나 혼자 풀어서 기분이 좋았다. 무엇보다 예상하지 못했던 효율성 테스트도 한 번에 통과해서 상당히 뿌듯하다. ㅎㅎ.

코드 설명

일단 주어진 숫자의 2진수의 1 개수를 구한다(1의 개수 구하기 아이디어는 위에 있다). 다음 무한 루프를 돌면서 임시 변수(tmp)에 answer를 넣어주고(answer에는 n+1을 넣어줘야 자기 자신을 비교하는 걸 막을 수 있다) tmp의 2진수 1의 개수를 세준다. 그리고 그 결과 값을 j에 넣어준다. 만일 먼저 계산한 i의 값과 j의 값이 같으면(즉, 이진수의 1 개수가 같다면) break를 한다. 그렇지 않다면, answer에다가 1을 더해주면 된다. 임시 변수(tmp)를 쓰는 이유는 answer 자체를 쓸 경우 answer이 0이 되어 최소값을 찾을 수 없기 때문이다.
조건 3에는 최소값이어야 된다고 했지만, 제일 먼저 1의 개수가 같은 수를 return하기 때문에 크게 상관하지 않아도 된다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
        
    int answer = n+1;
    int i, k;
    int j = 0;
    
    for(i=0;n!=0;i++) {
      n&=(n-1);
    }

    while(1){
        int tmp = answer;
        for(k=0; tmp!=0; k++){
            tmp&=(tmp-1);
        }
        j = k;
        if(i == j){
            break;
        }else{
            answer++;
        }
    }

    return answer;
}