[정글 알고리즘] - [중] - 백준2470- 투포인터 - 두 용액

처음엔 브루트포스로 풀면 될 것 같았지만, N이 최대 10만이라 O(N²)은 시간 초과가 난다. 이진탐색을 떠올렸지만 재귀 기준이 모호했고, 결국 정렬 + 투포인터가 핵심임을 깨달았다.

📋 문제 소개

항목	내용
문제 번호	백준 2470
난이도	골드 5
분류	정렬, 투포인터 (Two Pointers)
핵심 함수	.sort(), abs()
시간 제한	1초
입력	첫째 줄: 용액 수 N (2 ≤ N ≤ 100,000) 둘째 줄: N개의 정수 (각 -1,000,000,000 ~ 1,000,000,000)
출력	혼합 특성값이 0에 가장 가까운 두 용액의 특성값 (오름차순)

입력 예시	출력 예시
5 -2 4 -99 -1 98	-99 98

❌ 브루트포스 - O(N²)로 시간 초과

처음 떠오르는 방법은 두 수를 모두 골라 합의 절댓값이 가장 작은 쌍을 찾는 것이다.

# 브루트포스 - 시간 초과 코드
n = int(input())
arr = list(map(int, input().split()))

best = float('inf')
ans = [arr[0], arr[1]]

for i in range(n):
    for j in range(i+1, n):      # 모든 쌍 탐색
        s = arr[i] + arr[j]
        if abs(s) < best:
            best = abs(s)
            ans = [arr[i], arr[j]]
            if best == 0:        # 합이 0이면 즉시 종료
                break

ans.sort()
print(ans[0], ans[1])

N	비교 횟수 (N×(N-1)/2)	판정
1,000	약 500,000	✅ 통과
10,000	약 50,000,000	⚠️ 경계
100,000	약 5,000,000,000	❌ 시간 초과

핵심 포인트: N=100,000일 때 약 50억 번의 연산이 필요하다. Python은 초당 약 1~2천만 번 연산 가능하므로 절대 1초 안에 끝나지 않는다.

🤔 이진탐색 vs 투포인터 - 어떻게 다른가

이진탐색도 O(N log N) 접근이지만, 이 문제는 "두 값의 합이 0에 가장 가까운 것"을 구하므로 기준점 하나를 고정하고 나머지를 이진탐색하는 방식이 된다. 가능하지만 구현이 복잡하다.

접근법	시간 복잡도	구현 난이도	이 문제 적합도
브루트포스	O(N²)	⭐ 쉬움	❌ 시간 초과
정렬 + 이진탐색	O(N log N)	⭐⭐⭐ 복잡	⚠️ 가능하지만 복잡
정렬 + 투포인터	O(N log N)	⭐⭐ 보통	✅ 최적

왜 투포인터가 자연스러운가?
정렬 후 배열의 양 끝을 가리키는 두 포인터를 좁혀가면, 합이 음수 → left를 오른쪽으로, 합이 양수 → right를 왼쪽으로 이동하는 규칙만으로 모든 경우를 탐색할 수 있다. 재귀 없이 while 루프 하나면 충분하다.

💡 투포인터 핵심 아이디어

전제: 배열을 오름차순 정렬한다.

정렬된 배열: [-99, -2, -1, 4, 98]
                       ↑ left=0                                    ↑ right=4

현재 합(s)	의미	행동	이유
s < 0	합이 너무 작다	left += 1	left를 오른쪽으로 → 더 큰 값으로 교체
s > 0	합이 너무 크다	right -= 1	right를 왼쪽으로 → 더 작은 값으로 교체
s == 0	완벽한 쌍 발견	break	더 이상 탐색할 필요 없음

왜 이 규칙이 맞는가? 배열이 정렬되어 있으므로, left를 오른쪽으로 움직이면 합이 증가하고, right를 왼쪽으로 움직이면 합이 감소한다. 최솟값 방향으로만 포인터를 이동하면 모든 최적 쌍을 탐색할 수 있다.

🔍 단계별 시뮬레이션

입력: -2 4 -99 -1 98 → 정렬 후: [-99, -2, -1, 4, 98]

단계	left	right	arr[left]	arr[right]	합(s)	|s|	best 갱신?	행동
1	0	4	-99	98	-1	1	✅ best=1, ans=[-99,98]	s<0 → left+1
2	1	4	-2	98	96	96	❌ (96 > 1)	s>0 → right-1
3	1	3	-2	4	2	2	❌ (2 > 1)	s>0 → right-1
4	1	2	-2	-1	-3	3	❌ (3 > 1)	s<0 → left+1
종료	2	2	left == right → while 루프 종료

최종 답: -99 98 (합 = -1, |합| = 1 → 0에 가장 가까움)

추가 예시: [6, 4, 8] → 정렬: [4, 6, 8]

단계	arr[left]	arr[right]	합	best 갱신?	행동
1	4	8	12	✅ best=12, ans=[4,8]	s>0 → right-1
2	4	6	10	✅ best=10, ans=[4,6]	s>0 → right-1
종료	left == right → 종료. 최종 답: 4 6

🧩 코드 한 줄씩 이해하기

import sys
input = sys.stdin.readline   # (1) 빠른 입력

n = int(input())             # (2) 용액 수 입력
arr = list(map(int, input().split()))  # (3) 용액 특성값 리스트
arr.sort()                   # (4) 오름차순 정렬 (투포인터 전제)

left = 0                     # (5) 왼쪽 포인터 (가장 작은 값)
right = n - 1                # (6) 오른쪽 포인터 (가장 큰 값)
best = float('inf')          # (7) 현재까지 최소 |합| (초기값: 무한대)
ans = [arr[0], arr[1]]       # (8) 정답 저장 (초기값: 아무 쌍이나)

while left < right:          # (9) 두 포인터가 만나면 종료
    s = arr[left] + arr[right]   # (10) 현재 쌍의 합

    if abs(s) < best:            # (11) 더 0에 가까운 합 발견 시
        best = abs(s)
        ans = [arr[left], arr[right]]   # (12) 정답 갱신

    if s < 0:                    # (13) 합이 음수 → 더 큰 값 필요
        left += 1
    elif s > 0:                  # (14) 합이 양수 → 더 작은 값 필요
        right -= 1
    else:                        # (15) 합이 0 → 최적해
        break

print(ans[0], ans[1])        # (16) 오름차순 출력 (정렬됐으니 보장됨)

라인	설명	주의사항
(4)	arr.sort()	투포인터는 반드시 정렬된 배열에서만 동작
(7)	float('inf')	어떤 값과 비교해도 무조건 첫 번째에 갱신됨
(11)	abs(s) < best	≤가 아니라 <: 이미 최적이면 갱신 불필요
(9)	while left < right	같은 원소를 두 번 쓰면 안 되므로 < (같으면 안 됨)
(16)	print(ans[0], ans[1])	배열을 정렬했으므로 ans의 순서도 오름차순 보장

⚠️ 흔히 겪는 실수 분석

#	실수 유형	잘못된 코드	올바른 코드	문제점
1	정렬 안 함	left=0, right=n-1 (그냥 사용)	arr.sort() 먼저	포인터 이동 논리가 의미 없어짐
2	best 초기값 오류	best = 0	best = float('inf')	best=0이면 어떤 합도 갱신 안 됨 (모든 |합|≥0)
3	포인터 이동 방향 반대	if s<0: right-=1	if s<0: left+=1	합을 줄여야 하는데 더 줄어듦 → 무한루프/오답
4	while 조건 오류	while left <= right	while left < right	같은 원소 두 번 사용 가능해짐 (문제 조건: 서로 다른 두 용액)
5	재귀로 구현 시도	def solve(left, right): ... solve(...)	while left < right: ...	N=100,000 시 재귀 깊이 초과(RecursionError), 스코프 문제 발생

재귀 → while 루프로 바꿔야 하는 이유

❌ 재귀 방식	✅ while 루프 방식
best = float('inf') ans = [] def solve(left, right): global best, ans if left >= right: return s = arr[left] + arr[right] if abs(s) < best: best = abs(s) ans = [arr[left], arr[right]] if s < 0: solve(left+1, right) elif s > 0: solve(left, right-1) else: return solve(0, n-1)	best = float('inf') ans = [arr[0], arr[1]] while left < right: s = arr[left] + arr[right] if abs(s) < best: best = abs(s) ans = [arr[left], arr[right]] if s < 0: left += 1 elif s > 0: right -= 1 else: break
• global 변수 필요 → 코드 복잡 • N=100,000 → 재귀 100,000번 → RecursionError • 스택 메모리 낭비	• global 불필요 → 깔끔 • 재귀 깊이 제한 없음 • 메모리 효율적

⏱️ 시간 복잡도 분석

단계	연산	복잡도	N=100,000 기준
입력	N개 읽기	O(N)	100,000
정렬	arr.sort()	O(N log N)	약 1,700,000
투포인터	각 원소 최대 1번씩 방문	O(N)	100,000
전체	정렬이 병목	O(N log N)	✅ 충분히 통과

투포인터 O(N) 증명: left는 오른쪽으로만, right는 왼쪽으로만 이동한다. 즉 각 포인터의 이동 횟수 합계는 최대 N번이다. 두 포인터가 만나면 종료되므로 전체 루프 횟수 ≤ N.

✅ 최종 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()                        # 투포인터는 정렬이 전제

left = 0
right = n - 1
best = float('inf')               # 현재까지 |합|의 최솟값
ans = [arr[0], arr[1]]            # 정답 초기값 (아무 쌍이나)

while left < right:
    s = arr[left] + arr[right]

    if abs(s) < best:             # 더 0에 가까운 쌍 발견
        best = abs(s)
        ans = [arr[left], arr[right]]

    if s < 0:
        left += 1                 # 합이 음수 → 더 큰 값이 필요 → left 오른쪽
    elif s > 0:
        right -= 1                # 합이 양수 → 더 작은 값이 필요 → right 왼쪽
    else:
        break                     # 합이 0 → 완벽한 쌍, 즉시 종료

print(ans[0], ans[1])             # 정렬됐으므로 오름차순 보장

💬 마무리

고민하며 이진탐색 재귀 방향을 잡았지만, 이 문제의 핵심은 "정렬된 배열에서 두 끝의 합을 보고 어느 방향으로 좁힐지 결정"하는 투포인터였다. 재귀는 스코프와 RecursionError 함정이 있고, while 루프가 훨씬 직관적이다.

정렬 O(N log N) + 투포인터 O(N) = 전체 O(N log N)으로 N=100,000도 여유롭게 통과한다.