문제 소개
배열 deli가 주어지며, deli[i]는 i번째 음식의 맛 점수(맛있음의 정도)를 나타냅니다. 우리는 이 목록에서 만들 수 있는 서로 다른 "좋은 식사(good meal)"의 개수를 구해야 합니다. 답이 너무 커질 수 있으므로 결과는 10^9 + 7로 나눈 나머지를 반환합니다.
여기서 좋은 식사란 정확히 두 개의 서로 다른 음식으로 구성되어 있고, 두 음식의 맛 점수 합이 2의 거듭제곱인 식사를 의미합니다. 어떤 두 음식이든 골라서 좋은 식사를 만들 수 있습니다.
예를 들어 입력이 deli = [1, 7, 3, 6, 5]라면 출력은 3이 됩니다. (1, 3), (1, 7), (3, 5) 쌍을 만들 수 있는데, 각각의 합이 4, 8, 8로 모두 2의 거듭제곱이기 때문입니다.
해결 접근 방법
모든 가능한 쌍을 일일이 확인하는 무차별 대입 방식은 O(n²)의 시간이 걸려 비효율적일 수 있습니다. 대신 빈도 카운팅과 해시맵을 활용하면 효율적으로 해결할 수 있습니다.
핵심 아이디어는 간단합니다. 두 음식의 맛 점수 합이 반드시 2^n 형태여야 하므로, 한쪽 값 i가 정해지면 짝이 되는 값은 자동으로 2^n − i 로 결정됩니다. 따라서 각 값에 대해 가능한 모든 2의 거듭제곱 지수(0부터 21까지)를 검사하면서 해당 짝이 존재하는지만 확인하면 됩니다.
- m := 10^9 + 7
- count := 각 맛 점수 값의 등장 빈도를 저장한 맵
- ans := 0
- count에 있는 각 값 i에 대해 다음을 반복합니다.
- n을 0부터 21까지 반복하면서:
- j := 2^n − i
- j가 count에 존재한다면:
- i와 j가 같은 경우: ans := ans + count[i] × (count[i] − 1)
- 그렇지 않은 경우: ans := ans + count[i] × count[j]
- n을 0부터 21까지 반복하면서:
- (ans ÷ 2) mod m을 반환합니다.
i == j인 경우(예: 맛 점수가 1인 두 음식을 더해 2를 만드는 경우)에는 같은 값끼리의 쌍을 세기 위해 count[i] × (count[i] − 1)을 사용합니다. 또한 각 쌍은 양방향에서 한 번씩 중복으로 세어지므로, 마지막에 전체를 2로 나누어 올바른 개수를 얻습니다.
구현 예시
아래 파이썬 구현을 통해 더 잘 이해해 보겠습니다.
from collections import Counter
def solve(deli):
m = 10**9 + 7
count = Counter(deli)
ans = 0
for i in count:
for n in range(22):
j = (1<<n)-i
if j in count:
if i == j:
ans += count[i] * (count[i]-1)
else:
ans += count[i] * count[j]
return (ans // 2) % m
deli = [1,7,3,6,5]
print(solve(deli))
입력
[1,7,3,6,5]
출력
3
복잡도 분석
서로 다른 맛 점수의 종류 수를 k라고 할 때, 시간 복잡도는 O(k × 22), 즉 사실상 O(k)이며, 공간 복잡도는 빈도 맵 저장을 위해 O(k)입니다. 배열 길이 n에 대해 O(n²)이 소요되는 단순 완전 탐색보다 훨씬 효율적으로 문제를 해결할 수 있습니다.