문제 설명
숫자 n과 또 다른 값 x가 주어졌을 때, n이 x의 거듭제곱인지 판별해야 합니다. 이때 x는 항상 2의 거듭제곱 수라고 가정합니다.
예를 들어 입력이 n = 32768, x = 32라면 출력은 True가 됩니다. 32768은 32³(즉, 32의 세제곱)이기 때문입니다.
해결 접근 방식
이 문제는 비트 연산을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 2의 거듭제곱 판별: n이 0이 아니면서 n AND (n − 1)의 결과가 0이면, n은 2의 거듭제곱입니다. 예를 들어 8(1000₂)과 7(0111₂)을 AND 연산하면 0이 됩니다.
- 지수 계산: n이 1보다 큰 동안 n을 오른쪽 시프트(2로 나누기)하며 나눈 횟수를 cnt에 기록하면, 그 값이 곧 2의 지수가 됩니다.
- x의 지수 구하기: 보조 함수 find_pow_of_2를 사용해 x(c) 자체가 2의 몇 제곱인지, 즉 밑을 2로 하는 로그값을 재귀적으로 계산합니다.
- 마지막으로 n의 지수(cnt)가 x의 지수로 나누어 떨어지는지 확인하여 결과를 반환합니다.
전체 과정을 단계별로 정리하면 다음과 같습니다.
- cnt := 0으로 초기화합니다.
- n이 0이 아니고 (n AND (n − 1)) == 0인 경우:
- n > 1인 동안 n = n / 2, cnt += 1을 반복합니다.
- (cnt mod (밑을 2로 하는 로그 c)) == 0 여부를 반환합니다.
- 위 조건을 만족하지 않으면 False를 반환합니다.
예제 코드
아래 파이썬 구현을 살펴보면 더 잘 이해할 수 있습니다.
def find_pow_of_2(n): return (1 + find_pow_of_2(n / 2)) if (n > 1) else 0 def solve(n, c): cnt = 0 if n and (n & (n - 1)) == 0: while n > 1: n >>= 1 cnt += 1 return cnt % (find_pow_of_2(c)) == 0 return False n = 32768 x = 32 print(solve(n, x))
입력
32768, 32
출력
True