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

문제

문제 설명

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

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

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

 

제한사항

• n은 1,000,000 이하의 자연수 입니다.

입출력 예시

n	result
78	83
15	23

문제: 프로그래머스 스쿨 - 연습문제 - 다음 큰 숫자

프로그래머스

---

문제 풀이

유의사항

• 조건이 복잡하지 않고, 이진법으로 수를 나타내는 알고리즘은 O(logN)이기에, 단순 반복 작업으로 문제를 풀 수 있다.

풀이

• 핵심 아이디어: 특정 수의 이진법 표현의 1의 갯수를 센 후, 그보다 더 큰 모든 숫자에 대해 이진법 변환을 하여 1의 갯수가 같은 수를 찾으면 된다.

---

전체 코드

def solution(n):
    answer = n + 1

    cnt = count1(n)

    while(True):
        if count1(answer) == cnt:
            break
        answer += 1

    return answer

def count1(n): # 이진법 변환 시의 1의 갯수를 세는 함수
    cnt = 0

    while(n):
        cnt += (n%2)
        n //= 2
    return cnt