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

문제

출처

이해

입력

• 자연수 n
  • 범위: [1, 100만]

출력

• 조건을 만족하는 수 x

조건

1. x는 n보다 큰 자연수이다.
2. x와 n을 2진수로 나타낼 때, 1의 개수는 같다.
3. x는 1과 2를 모두 만족하는 수 중 가장 작은 수이다.

예시

입출력

입력: 
78

출력: 
83

접근

brute-force

문제에서 주어진 조건 그대로 n보다 큰 모든 자연수를 오름차순으로 조회하여, 2진법으로 표현했을 때 1의 개수를 세서, 만족하는 첫 번째 수를 return한다.

def solution(n):
    cnt = bin(n).count('1')
    answer = n + 1
    while bin(answer).count('1') != cnt:
        answer += 1
    return answer

패턴

여기서 멈추면 아쉽기 때문에 더 어려운 풀이를 생각해보았다.

우선 가장 간단한 케이스부터 생각을 해보자.

1 -> 10
11 -> 101
111 -> 1011
1111 -> 10111

1... 패턴은 쉽게 이해할 수 있다. 예를 들어 111 을 생각해보자. 111 에 대한 답은 1xxx 꼴이 된다. 3개의 1bit 중 한 개는 이미 사용하였으므로 남은 2개의 1bit를 가장 낮은 자리에 배치하면 답은 1011이 된다.

그런데 이 논리는 1...0... 과 같은 패턴에도 적용할 수 있다. 예를 들어 1100 을 생각해보자. 자리수가 같으면서 1100 보다 큰 수는 1101, 1110, 1111 인데 세 가지 모두 1bit의 수가 1100 보다 많기 때문에 정답에서 제외된다. 따라서 답은 1xxxx 꼴이 되는데 남은 1개의 1bit를 가장 낮은 자리에 배치하면 답은 10001이 된다.

그리고 계속하여 일반적인 패턴으로 확장시킬 수 있다. 일반적인 패턴에서 앞에서 살펴본 패턴을 찾아서 앞뒤로 나누고, 답을 구해서 합치는 것이다. 앞에서 살펴본 패턴은 당연히 뒷부분에 해당한다. 오른쪽에서부터 살펴봐서 처음 나오는 "01"을 찾았을 때, 1의 뒤로는 1...0... 또는 1... 패턴이 될 수 밖에 없다. 이렇게 전체를 부분으로 나누어서 뒷부분의 답을 따로 구하고, 다시 더하면 전체의 답이 된다. 단, 더할 때 carry가 생겨서 1bit의 수가 변하는 일이 없어야 한다. 물론 carry가 생기는 일은 없는데, 뒷부분의 답을 구하면 한 자리가 늘어나게 되고, 이를 다시 더할 때 분리했던 부분의 "01" 이 "1x"가 되기 때문이다. (정확히는 "10" 이 된다.)

일반적인 패턴을 해결하는 예를 살펴보자.

> 10101
= 10100 + 1
= 10100 + 10
= 10110

> 11010110
= 11010000 + 110
= 11010000 + 1001
= 11011001

구현

def solution(n):
    # b가 '1...0...' 패턴일 때 답을 return
    def get(b):
        one = b.count('1')
        return '1' + '0'*(len(b)-one+1) + '1'*(one-1)
    
    answer = 0
    b = bin(n)[2:]
    
    # 가장 오른쪽에 위치한 '01'을 찾는다.
    check = ''.join(reversed(b)).find('10')
    
    # 없으면 전체가 '1...0...' 패턴
    if check == -1:
        answer = int(get(b), 2)
    else:
        check = -(check + 2)
        # '01'이 있으면 전체를 두 부분으로 쪼개서 해결
        answer = int(b[:check]+get(b[check+1:]), 2)
        
    return answer