문제 소개
좋은 식사(Good Meal)란 정확히 두 가지 서로 다른 음식으로 구성되며, 두 음식의 맛 점수(deliciousness)의 합이 정확히 2의 거듭제곱(1, 2, 4, 8, 16, ...)이 되는 식사를 말합니다. 배열 속에서 어떤 두 음식을 골라도 좋은 식사를 만들 수 있습니다.
정수 배열 arr가 주어지고, arr[i]는 i번째 음식의 맛 점수라고 할 때, 이 배열로 만들 수 있는 서로 다른 좋은 식사의 개수를 구하는 것이 목표입니다. 결과가 매우 커질 수 있기 때문에 일반적으로 10⁹ + 7로 나눈 나머지를 반환합니다.
예제 1
입력
arr[] = {1, 3, 5, 7, 9}출력
4
설명 − 가능한 좋은 식사는 (1,3), (1,7), (3,5), (7,9)입니다. 각각의 합은 4, 8, 8, 16으로 모두 2의 거듭제곱입니다.
예제 2
입력
arr[] = {1, 1, 1, 3, 3, 3, 7}출력
15
설명 − (1,1) 조합이 3가지, (1,3) 조합이 9가지, (1,7) 조합이 3가지이므로 총 15가지입니다.
해결 접근 방법
양의 정수로 이루어진 배열을 입력으로 받습니다.
countPairs함수는 배열의 모든 원소를 정수 리스트로 전달받습니다.입력 배열을 오름차순으로 정렬합니다.
배열의 각 원소에 대해, 해당 원소와 만들 수 있는 최대 합(자기 자신과의 합
d + d) 이하의 모든 2의 거듭제곱 후보값을 순회하며, 지금까지 등장한 값 중 보완값(2의 거듭제곱 − 현재 값)의 개수를 누적해 쌍을 셉니다.
이 방식은 해시맵(defaultdict)을 활용해 각 원소를 한 번씩만 처리하므로, 전체 시간 복잡도는 O(n · log M)(M은 배열 내 최댓값)로 매우 효율적입니다.
구현 예제
from collections import defaultdict
from typing import List
class Solution:
def countPairs(self, arr: List[int]) -> int:
"""
elem1 + elem2 == 2 ** i 인 쌍을 찾습니다.
즉, elem2 == 2 ** i - elem1 입니다.
"""
MOD = 10 ** 9 + 7
ans = 0
seen = defaultdict(int)
arr.sort()
for d in arr:
n = 1
while n <= d + d:
ans = (ans + seen[n - d]) % MOD
n <<= 1
seen[d] += 1
return ans
sol1 = Solution()
print(sol1.countPairs([1, 1, 1, 3, 3, 3, 7])) # 출력: 15실행 결과
15
코드 동작 원리
배열을 정렬한 뒤 왼쪽부터 차례대로 탐색하면서, 현재 값 d보다 앞서 등장한 값들만 seen 딕셔너리에 기록합니다. 각 단계에서 n을 1부터 시작해 비트 시프트(<<= 1)로 2배씩 늘려가며 d + d 이하의 모든 2의 거듭제곱을 검사하고, seen[n − d]에 저장된 개수만큼 정답에 더합니다. 마지막으로 현재 값 d를 seen에 추가하면, 같은 값이 여러 번 나오는 경우(예제 2의 (1,1), (1,3)처럼)도 중복 없이 정확히 셀 수 있습니다.