듀엣 파트너를 어떻게 고를까?
노래 연습 앱 '하모니'에는 멤버마다 음정 점수가 있습니다. 두 명이 함께 부를 때, 두 점수의 합이 목표 화음값 T에 가까울수록 듀엣이 잘 어울립니다.
그런데 합이 정확히 T가 되는 두 명이 없을 수도 있어요. 그래서 목표는 "합이 T가 되는 쌍"이 아니라 "합이 T에 가장 가까운 쌍"을 찾는 것입니다.
예: 점수가
[12, 18, 25, 33, 41, 50]이고 목표가 60이라면? 답은 59 (18 + 41). 차이가 단 1이라 가장 가깝습니다.
가장 단순한 방법과 그 한계
가장 먼저 떠오르는 건 모든 두 명 조합을 다 따져보는 것입니다. 합을 구하고 |합 - T|가 가장 작은 쌍을 기억하면 됩니다.
문제는 멤버가 N명이면 조합이 약 N²/2개라는 점이에요. N이 10만이면 50억 번 — 시간 안에 못 끝냅니다. O(n²)는 너무 느립니다.
핵심 아이디어: 정렬을 무기로 (양끝 투 포인터)
여기서 중요한 전제가 있습니다. 점수가 오름차순으로 정렬돼 있다는 것이죠. 이걸 이용하면 모든 쌍을 보지 않고도 답을 찾을 수 있습니다.
포인터 두 개를 양 끝에 두고 시작합니다.
- •
left는 가장 작은 값(왼쪽 끝),right는 가장 큰 값(오른쪽 끝) - •두 값의 합을 목표 T와 비교합니다.
- 합 < T → 합이 부족하다 → 더 큰 값이 필요 → left를 오른쪽으로 한 칸
- 합 > T → 합이 넘친다 → 더 작은 값이 필요 → right를 왼쪽으로 한 칸
- 합 == T → 차이 0, 더 가까울 수 없으니 바로 정답
- •매 쌍마다 |합 - T|를 지금까지의 최선과 비교해 더 가까우면 best를 갱신합니다.
이걸 left와 right가 만날 때까지 반복하면 끝입니다.
"왜 한쪽만 움직여도 안전할까?"
처음 보면 "한쪽 포인터만 움직이면 놓치는 쌍이 생기지 않을까?" 걱정됩니다. 하지만 정렬돼 있기 때문에 안전합니다.
합이 T보다 작을 때를 생각해봅시다. 지금 right는 오른쪽 끝이라 가능한 가장 큰 값과 짝지은 상태예요. 그런데도 합이 작다면, right를 더 줄여서 만드는 쌍들은 합이 더더욱 작아질 뿐 — 절대 T에 더 가까워지지 않습니다. 그러니 그 쌍들은 버려도 안전하고, 유일하게 합을 키울 방법인 left++만 하면 됩니다.
합이 T보다 클 때도 대칭으로 같은 논리가 성립합니다. 그래서 각 포인터는 한 방향으로만 움직이고, 전체가 O(n)에 끝납니다.
한눈에 보는 복잡도
| 방법 | 시간복잡도 | 비고 |
|---|---|---|
| 모든 쌍 비교 | O(n²) | 단순하지만 N이 크면 불가 |
| 양끝 투 포인터 | O(n) | 정렬 전제, 각 포인터 한 방향 이동 |
| (정렬이 안 돼 있다면) | O(n log n) | 먼저 정렬 후 투 포인터 |
자주 하는 실수
- •best 초기화 누락: 첫 쌍을 미리 best로 잡아두지 않으면 비교 기준이 없습니다.
- •차이를 부호 없이 비교하지 않음: 반드시 절댓값 |합 - T|로 비교해야 위/아래 모두 공평하게 다룹니다.
- •정렬 확인 누락: 입력이 정렬돼 있다는 보장이 없으면 먼저 정렬해야 합니다.
- •종료 조건:
left < right동안만 반복해야 같은 사람을 두 번 고르지 않습니다.
알고노트에서 직접 확인하세요
두 포인터가 양끝에서 어떻게 좁혀 들어오는지, 그리고 어느 순간 best가 갱신되는지는 눈으로 봐야 확실히 이해됩니다. 합이 목표보다 클 때와 작을 때 포인터가 어떻게 반응하는지 한 스텝씩 따라가 보세요.