알고리즘 연습 [다음 큰 숫자]
다음 큰 숫자
문제
어떤 수 N(1≤N≤1,000,000) 이 주어졌을 때, N의 다음 큰 숫자는 다음과 같습니다.
N의 다음 큰 숫자는 N을 2진수로 바꾸었을 때의 1의 개수와 같은 개수로 이루어진 수입니다.
1번째 조건을 만족하는 숫자들 중 N보다 큰 수 중에서 가장 작은 숫자를 찾아야 합니다.
예를 들어, 78을 2진수로 바꾸면 1001110 이며, 78의 다음 큰 숫자는 83으로 2진수는 1010011 입니다.
N이 주어질 때, N의 다음 큰 숫자를 찾는 nextBigNumber 함수를 완성하세요.
나의 풀이
def nextBigNumber(n):
answer = n + 1
while bin(n).count('1') != bin(answer).count('1'):
answer += 1
return answer
n의 이진수 개수와 일치할 때까지 1을 더하는 방식으로 풀었다.
- bin() : 이진수 전환
- 이진수를 int로 바꾸려면 int(‘0b이진수값’, 2)
- bin().count(‘1’)로 1의 개수를 계산할 수 있음