문제 개요
하나의 숫자 n이 주어졌을 때, n의 이진 표현(binary representation)이 회문(palindrome)인지 판별하는 문제입니다.
예를 들어 입력값이 n = 9라고 가정해 보겠습니다. 9의 이진 표현은 1001이며, 앞에서 읽으나 뒤에서 읽으나 같기 때문에 회문입니다. 따라서 출력 결과는 True가 됩니다.
해결 접근 방법
이 문제는 숫자의 이진 비트를 뒤집은(reverse) 값이 원래 값과 동일한지 비교하는 방식으로 해결할 수 있습니다. 알고리즘의 핵심 단계는 다음과 같습니다.
- 결과값 ans를 0으로 초기화합니다.
- num이 0보다 큰 동안 아래 과정을 반복합니다.
- ans를 왼쪽으로 1비트 시프트합니다 (ans = ans * 2).
- num의 최하위 비트가 1, 즉 num이 홀수라면 ans에 XOR 연산으로 1을 설정합니다.
- num을 오른쪽으로 1비트 시프트합니다 (num = num / 2).
- 반복이 종료되면 ans에는 원래 숫자의 비트 순서가 뒤집힌 값이 저장됩니다.
마지막으로 원래 숫자 n과 뒤집힌 값 rev가 같은지 비교하면, 해당 숫자의 이진 표현이 회문인지 쉽게 판별할 수 있습니다.
구현 예제
def reverse_binary(num):
ans = 0
while num > 0:
ans = ans << 1 # 결과값을 왼쪽으로 한 비트 시프트
if num & 1 == 1: # 현재 최하위 비트가 1인지 확인
ans = ans ^ 1 # 1이라면 ans의 마지막 비트를 1로 설정
num = num >> 1 # num을 오른쪽으로 한 비트 시프트
return ans
def solve(n):
rev = reverse_binary(n) # 비트를 뒤집은 값 계산
return n == rev # 원래 값과 비교하여 회문 여부 반환
n = 9
print(solve(n))입력
9
출력
True
동작 과정 상세 설명
n = 9일 때의 실행 흐름을 단계별로 살펴보면 다음과 같습니다.
- 9의 이진 표현은 1001입니다.
- reverse_binary 함수가 각 비트를 역순으로 조합하여 1001을 그대로 반환합니다.
- 원래 값 n(9)과 뒤집힌 값 rev(9)가 일치하므로 최종적으로 True가 출력됩니다.
반면 n = 10인 경우를 생각해 보면, 10의 이진 표현은 1010이고 비트를 뒤집으면 0101(십진수 5)이 됩니다. 원래 값과 다르므로 False가 출력되며, 이를 통해 회문 여부가 올바르게 판별됨을 확인할 수 있습니다.