숫자로 이루어진 배열 nums가 있다고 가정해 보겠습니다. 이때 비트 AND(bitwise AND) 연산의 결과가 2의 거듭제곱이 되는 부분 집합이 배열 안에 존재하는지 확인해야 합니다.
예를 들어 입력이 nums = [22, 25, 9]라면 출력은 True입니다. 부분 집합 {22, 9}의 이진수 표현은 각각 10110과 1001이며, 두 수의 비트 AND 결과는 10000, 즉 16(=2⁴)으로 2의 거듭제곱이기 때문입니다.
알고리즘 접근 방식
핵심 아이디어는 간단합니다. 어떤 부분 집합의 비트 AND 결과가 2의 거듭제곱(예: 2k)이 되려면, 그 부분 집합에 속한 모든 원소는 k번째 비트가 반드시 1로 설정되어 있어야 합니다. 따라서 각 비트 위치별로 해당 비트를 포함하는 숫자들만 모아 AND 연산을 수행한 뒤, 그 결과가 2의 거듭제곱인지 검사하면 됩니다.
구체적인 풀이 단계는 다음과 같습니다.
- MAX := 32 — 최대 32비트 정수를 가정합니다.
solve()함수를 정의하고 배열nums를 인자로 전달합니다.- 배열의 크기가 1이라면,
nums[0]이 2의 거듭제곱일 때 true를, 그렇지 않으면 false를 반환합니다. total := 0으로 초기화한 뒤, i를 0부터 MAX-1까지 반복하면서total := total OR 2^i를 수행하여 모든 비트가 1로 설정된 마스크를 만듭니다.- i를 0부터 MAX-1까지 반복하면서 다음을 수행합니다.
ret := total로 초기화합니다.- j를 0부터 배열 크기까지 반복하면서,
nums[j] AND 2^i의 결과가 0이 아니면(즉, 해당 비트가 설정되어 있으면)ret := ret AND nums[j]를 수행합니다. - 반복이 끝난 후
ret이 2의 거듭제곱이면True를 반환합니다.
- 모든 비트 위치에서 조건을 만족하지 못하면
False를 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
예제 코드
MAX = 32
def is_2s_pow(v):
return v and (v & (v - 1)) == 0
def solve(nums):
if len(nums) == 1:
return is_2s_pow(nums[0])
total = 0
for i in range(0, MAX):
total = total | (1 << i)
for i in range(0, MAX):
ret = total
for j in range(0, len(nums)):
if nums[j] & (1 << i):
ret = ret & nums[j]
if is_2s_pow(ret):
return True
return False
nums = [22, 25, 9]
print(solve(nums))
입력
[22, 25, 9]
출력
True
코드 설명
is_2s_pow(v) 함수는 v & (v - 1) == 0이라는 널리 알려진 비트 트릭을 활용해 v가 2의 거듭제곱인지 판별합니다. 2의 거듭제곱은 이진수로 딱 한 자리만 1이므로, 여기서 1을 빼면 그 비트 아래 자릿수가 모두 1로 바뀌고 AND 연산 결과는 0이 됩니다.
solve() 함수는 각 비트 위치 i에 대해, i번째 비트가 설정된 숫자들만 골라 누적 AND를 계산합니다. 그 결과가 2의 거듭제곱이라면 조건을 만족하는 부분 집합이 존재한다는 의미이므로 즉시 True를 반환합니다. 시간 복잡도는 O(MAX × N)으로, 여기서 N은 배열의 길이입니다.