문제
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12911
자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의한다.
조건 1. n의 다음 큰 숫자는 n보다 큰 자연수다.
조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같다.
조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수이다.
예를 들어 78(1001110)의 다음 큰 숫자는 83(1010011)입니다. 자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 반환하는 함수를 작성하라.
접근
자연수 n을 이진수로 변환한 뒤, 덧셈 연산에 의해 자리값이 01에서 10으로 바뀌는 지점을 찾는다. 남은 오른쪽 자리값은 1의 개수가 같은 최솟값으로 채운다.
문제 설명 예시의 78(1001110)로 풀어 설명하면 다음과 같다.
78의 이진수에서 1씩 더하다가 자리값 01이 10으로 변경되는 지점은 노란색 표시한 부분이다.
찾은 지점의 값을 변경하고,
조건 1, 2를 만족하는 가잔 작은 값이 될 수 있도록 변경 지점의 오른쪽 110 부분을 1과 0의 개수가 같은 최솟값 011로 변경한다.
코드
코드는 다음과 같다.
1. 자연수 n을 이진수 문자열로 변환한다.
이진수 문자열에는 이진수를 나타내는 prefix '0b'가 붙어있는데, 계산 편의를 위해 이 부분은 삭제한다.
또, 1111과 같아 1로만 이루어진 수를 편하게 처리할 수 있도록 맨앞에 '0'을 붙여준다.
bin_n = '0' + bin(n)[2:]
2. 이진수 문자열에서 '01'에 해당하는 위치를 찾는다.
탐색은 오른쪽 끝에서부터 시작한다.
idx_swap = bin_n.rfind('01')
idx_residue = idx_swap + 2찾으면 0의 위치가 idx_swap으로 저장된다.
연산 편의를 위해 idx_residue라는 변수로 자릿값 변경 지점의 오른쪽으로 남는 값의 시작점을 저장한다. idx_swap과 idx_swap + 1의 자릿값이 변경되므로 idx_swap + 2가 변경 지점 오른쪽으로 남는 값의 시작점이 된다.
3. 오른쪽으로 남는 값의 1의 개수와 0의 개수를 구한다.
cnt_zero = bin_n[idx_residue:].count('0')
cnt_one = bin_n[idx_residue:].count('1')
4. 다음 큰 수의 이진수 문자열을 만든다.
answer = bin_n[:idx_swap] + bin_n[idx_swap:idx_residue][::-1] + '0' * cnt_zero + '1' * cnt_one
5. 다음 큰 수의 이진수 문자열을 십진수로 변환하여 반환한다.
int(answer, base=2)
전체 코드는 다음과 같다.
def solution(n):
bin_n = '0' + bin(n)[2:]
idx_swap = bin_n.rfind('01')
idx_residue = idx_swap + 2
cnt_zero = bin_n[idx_residue:].count('0')
cnt_one = bin_n[idx_residue:].count('1')
answer = bin_n[:idx_swap] + bin_n[idx_swap:idx_residue][::-1] + '0' * cnt_zero + '1' * cnt_one
return int(answer, base=2)
참고 문서
https://latte-is-horse.tistory.com/186