Programmers - 다음 큰 숫자

---

title: Programmers - 다음 큰 숫자
date: 2022-07-15
tags:

• Algorithm

---

https://school.programmers.co.kr/learn/courses/30/lessons/12911

문제 요약

자연수 n이 존재한다. n의 2진수 표현시 1의 개수가 같은 수 중 n보다 크며 가장 작은 수를 return한다.

문제 풀이

처음부터 2진수 표현을 명시함으로써 비트 연산 문제임을 알려주었다.
1의 개수가 같아야 하므로 2진수 표현으로 가장 작은 비트부터 비교를 시작한다.
01(2)가 나올 경우, 10(2) 로 바꾼 후 우측에 존재하는 1의 개수를 센다.
1이 0개라면 값을 그대로, n개라면 2^n -1 을 더해준다. 이것이 가장 작은 수이다.
이러한 문제처럼 복잡한 비트 연산은 프로그램을 보더라도 바로 이해하기 어렵다.
현업에서 이렇게 비트 연산같은 로우 레벨을 사용해야 할 때, 좋은 프로그램과 성능 중 무엇을 우선시해야 하는지 잘 모르겠다.

추가적으로, 다른 사람이 푼 풀이 중 아래와 같은 풀이가 존재한다.

int num = bitset<20>(n).count();
while (bitset<20>(++n).count() != num);
return n;

bitset을 이용한 매우 직관적인 알고리즘이다. 좋은 프로그램이나, 성능면에서는 과연 좋은가? 라는 의문이 든다.
n을 1씩 증가하여 1의 개수를 세는 알고리즘이다. 작은 수에서는 문제가 없으나, 수가 커지면 문제가 생긴다.
0111....11 이라는 수를 가정하자. 물론 문제에서 제시된 조건을 벗어나는 매우 큰 수이지만, 이 또한 고려해야 한다.
문제에 적합한 바로 다음 수는 1011...11 이다. 32비트 기준으로 약 11억의 차이가 있다.
해당 알고리즘으로 11억번 이상의 연산이 이루어지는 것이다.
매우 직관적인 프로그램이지만, 성능 측면에서 좋은 프로그램이 아니다.

프로그램

int solution ( int n )
{
    int iTemp = n ;
    int iIndex = 0 ;
    int iReturn = 0 ;



    for ( int i = 0 ; i < 31 ; ++i )
    {
        if ( 1 == ( ( n & ( 3 << i ) ) >> i ) )
        {
            iReturn = n + ( 1 << i ) ;
            iIndex = i - 1 ;

            break ;
        }
    }

    iTemp = 0 ;

    for ( int i = iIndex ; i >= 0 ; --i )
    {
        if ( 1 == ( ( iReturn & ( 1 << i ) ) >> i ) )
        {
            ++ iTemp ;
        }
    }


    ++ iIndex ;
    if ( 0 != iTemp )
    {
        iReturn = ( ( iReturn >> iIndex ) << iIndex ) + ( 1 << iTemp ) - 1 ;
    }

    return iReturn ;
}