[프로그래머스] 다음 큰 숫자 찾기

이번에 풀어본 문제는 프로그래머스의 다음 큰 숫자문제입니다.

문제 url은 이거입니당 문제

n의 다음 큰 숫자라는건 n보다 큰 수 중에 2진수로 변환했을 때 n과 1의 개수가 동일한 것 중 가장 작은 수를 말합니다.

처음 문제를 보고 바로 생각난건 당연히 while… 알고리즘을 풀다 보면 뭔가 실행 시간 때문에 단순하게 생각난걸 사용하기가 꺼려지는..ㅠㅠ

그래도 만점이 나오네요!!!

처음 while을 사용한 것을 배척하고 조사해본 방법은 bit operation를 사용한 방법입니다.

역시 STL이건 뭐건 가장 중요한건 기초 지식인 듯...

사용한 bit operation의 특징은 숫자 n이 있으면 n-1과 and 연산을 하는 방법입니다.

n&n-1을 하게 되면 LSB에 가까운 1이 없어지게 되는데, 이렇게 되면 연산은 총 1의 개수만큼 연산하게 되는 거죠.

예를 들어서, n = 14 = 1110이라고 한다면 1의 개수는 1이 되야겠죠.

step 1. n = n & n-1 1110 & 1101 = 1100

step 2. n = n & n-1 1100 & 1001 = 1000

step 3. n = n & n-1 1000 & 0111 = 0000

총 3번의 연산을 하게 되네요.

코드는 이렇게~

#include <string>
#include <vector>

using namespace std;
int bitCount(int n)
{
    int cnt = 0;
    
    for(cnt = 0; n!=0; cnt++)
    {
        n &= (n-1);
    }
    /*
    while(n!=0)
    {
        if(n%2==1) cnt++;
        n /= 2;
    }*/
    return cnt;
    
}
int solution(int n) {
    int answer = 0;
    int nCount = bitCount(n);
    for(answer=n+1;;answer++)
    {
        if(nCount == bitCount(answer)) break;
    }
            
    return answer;
}

프로그래머스 코드를 보면 vector를 include하는 것을 알 수 있는데, 찾아보니까 vector로 풀 수 있는 방법이 있다고 하네요.. 한번 알아봐야지

그럼 안녕~