문제 개요
숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 이때 인덱스 쌍 (i, j) 중에서 i < j를 만족하고, nums[i] + nums[j]의 값이 어떤 정수 k ≥ 0에 대해 2^k(2의 거듭제곱)가 되는 쌍의 개수를 구하는 것이 목표입니다.
예를 들어 입력이 nums = [1, 2, 6, 3, 5]라면 출력은 3이 됩니다. 조건을 만족하는 세 가지 쌍은 다음과 같습니다.
- (6, 2): 합이 8 (= 2³)
- (5, 3): 합이 8 (= 2³)
- (1, 3): 합이 4 (= 2²)
풀이 접근 방법
모든 쌍을 일일이 확인하는 O(n²) 완전 탐색 대신, 해시맵(Counter)을 활용하면 더 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
결괏값을 저장할 변수 res := 0으로 초기화합니다.
c := 지금까지 등장한 각 요소의 빈도수를 저장하는 맵(Counter)을 준비합니다.
nums의 각 원소 x에 대해 다음을 수행합니다.
- j를 0부터 31까지 반복하면서 res := res + c[(2^j) − x]를 누적합니다. 즉, 현재 값 x와 더했을 때 2의 거듭제곱이 되는 값이 이전에 몇 번 나왔는지 확인합니다.
- 확인이 끝난 후 c[x] := c[x] + 1로 현재 값의 빈도를 1 증가시킵니다.
최종적으로 res를 반환합니다.
32비트 정수 범위 내에서 가능한 2의 거듭제곱은 최대 32개이므로, 전체 시간 복잡도는 O(n × 32) = O(n)으로 매우 효율적입니다.
예제 코드
아래 파이썬 구현을 통해 동작 과정을 더 잘 이해할 수 있습니다.
from collections import Counter
def solve(nums):
res, c = 0, Counter()
for x in nums:
for j in range(32):
res += c[(1 << j) - x]
c[x] += 1
return res
nums = [1, 2, 6, 3, 5]
print(solve(nums))입력
[1, 2, 6, 3, 5]
출력
3
정리
이 알고리즘은 각 원소를 순회하면서 현재까지 등장한 값들의 빈도를 Counter에 기록하고, (2^j − x)에 해당하는 값이 이미 존재하는지 조회함으로써 조건을 만족하는 쌍을 빠르게 셉니다. 완전 탐색(O(n²))보다 훨씬 빠르게 결과를 얻을 수 있어, 입력 크기가 큰 경우에도 실용적인 해법입니다.