Python에서 두 숫자의 이진수 표현이 아나그램인지 확인하는 방법

두 개의 숫자 x와 y가 주어졌을 때, 이 숫자들의 이진수(binary) 표현이 서로 아나그램(anagram) 관계인지 확인하는 문제를 생각해 보겠습니다.

예를 들어 입력이 x = 9, y = 12라고 가정해 봅시다. 9의 이진수 표현은 1001이고, 12의 이진수 표현은 1100입니다. 두 숫자 모두 1이 두 번, 0이 두 번 나타나므로 자릿수의 구성이 동일합니다. 따라서 출력은 True가 됩니다.

문제 해결 접근 방식

두 이진수가 아나그램 관계인지 판단하는 핵심 조건은 매우 간단합니다. 아나그램이 되려면 0과 1의 개수가 각각 같아야 하기 때문에, 결국 두 숫자에 포함된 1비트(set bit)의 개수만 비교하면 됩니다.

• x와 y에서 1의 개수가 서로 같다면
  • True를 반환합니다.
• 그렇지 않다면 False를 반환합니다.

구현 예제

아래 코드는 비트 연산을 활용해 숫자에 포함된 1비트의 개수를 세는 함수와, 이를 이용해 아나그램 여부를 판별하는 함수로 구성되어 있습니다.

def set_bit_count(num) :
    cnt = 0
    while num:
        cnt += num & 1
        num >>= 1
    return cnt

def solve(x, y) :
    if set_bit_count(x) == set_bit_count(y):
        return True
    return False

x = 9
y = 12
print(solve(x, y))

입력

9, 12

출력

True

코드 설명

set_bit_count(num) 함수는 숫자를 오른쪽 시프트(>>=)하면서 마지막 비트(num & 1)가 1인지 확인하고, 1비트의 총 개수를 반환합니다. solve(x, y) 함수는 두 숫자의 1비트 개수가 동일한지 비교하여 결과를 반환합니다.

참고로 Python에서는 bin(num).count('1') 또는 내장 함수 num.bit_count()(Python 3.10 이상)를 사용하면 더 간결하게 1비트 개수를 구할 수 있습니다.