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

다음 큰 숫자

문제 링크

다음 큰 숫자

분석

자연수 n보다 다음 큰 숫자를 찾아야합니다.
다음 큰 숫자에 대한 정의는 다음과 같습니다.

• n보다 큰 자연수 입니다.
• n의 다음 큰 숫자와 n를 2진수로 변환 했을 때 1의 개수가 같습니다.
• 1번과 2번을 만족하는 수 중 가장 작은 수 입니다.

가장 직관적이고 쉬운 방법은 브루트포스로 접근해 숫자를 하나씩 증가하며 확인하는 방법입니다.
이 경우 n보다 큰 숫자에 대해 매번 비트 개수를 세어주어야 합니다.
현재 문제의 경우 숫자 제한 값이 크지 않기 때문에 시간초과가 발생하지 않고 풀 수 있습니다.

다음 방법으로는 비트를 조작하여, 낮은 쪽 비트에서 01로 된 패턴을 찾아 0을 1로 1을 0으로 바꾸는 방법이 있습니다.
만약 중간에 있는 비트에서 01로 된 패턴을 찾고, 변경한 경우 그 이후 비트의 1은 가장 낮은 쪽 비트로 몰아야합니다.
이 과정에서 가장 낮은 쪽 비트로 모는 것은 큰 수 중에서 최대한 작은 값으로 만들어야하기 때문입니다.
만약 01로 이루어진 패턴이 없을 경우 가장 높은 쪽 비트의 앞에 0을 추가하고, 01패턴을 수정하는 작업을 진행하면 됩니다.

풀이

저는 브루트포스 방법만으로 문제를 풀이했습니다.

// 2진수로 변환하며, 1의 개수를 세주는 함수
int GetOneCount(int targetNumber)
{
    int count = 0;
    
    while (targetNumber != 0)
    {
        // 현재 수의 가장 낮은 비트가 1인 경우
        if (targetNumber % 2 == 1)
        {
            ++count;
        }
        
        // 현재 수의 가장 낮은 비트를 제거한다.
        // >>= 1 (시프트)와 같은 결과물
        targetNumber /= 2;
    }
    
    return count;
}

int solution(int n) {
    int answer = n + 1;
    
    // n이 가진 1의 개수를 캐싱한다.
    int oneCount = GetOneCount(n);
    
    // 조건에 맞는 수를 찾을 때까지 반복한다.
    while (true)
    {
        // 조건에 맞는 수를 찾은 경우 반복문 탈출
        if (GetOneCount(answer) == oneCount)
        {
            break;
        }
        
        ++answer;
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n \times log n)$입니다.

• 조건에 맞는 수를 찾는 반복문 $O(n)$
• 비트에서 1의 개수를 반환하는 함수 $O(log n)$
• $O(n) \times O(log n)$

공간 복잡도는 추가적인 공간을 사용하지 않기 때문에 $O(1)$입니다.

테스트 성능

정확성 테스트

테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.21MB)
테스트 4 〉 통과 (0.01ms, 4.22MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.14MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 4.21MB)
테스트 9 〉 통과 (0.01ms, 4.15MB)
테스트 10 〉 통과 (0.01ms, 4.22MB)
테스트 11 〉 통과 (0.01ms, 4.45MB)
테스트 12 〉 통과 (0.01ms, 4.21MB)
테스트 13 〉 통과 (0.01ms, 4.15MB)
테스트 14 〉 통과 (0.01ms, 4.17MB)

효율성 테스트

테스트 1 〉 통과 (0.01ms, 3.79MB)
테스트 2 〉 통과 (0.01ms, 3.81MB)
테스트 3 〉 통과 (0.01ms, 3.81MB)
테스트 4 〉 통과 (0.01ms, 3.82MB)
테스트 5 〉 통과 (0.01ms, 3.82MB)
테스트 6 〉 통과 (0.01ms, 3.54MB)