백준 1253: 좋다(파이썬)

💡 세 수의 합 문제, 어떻게 효율적으로 접근할까?

🧠 문제 배경

다음과 같은 조건이 주어진다:

"N개의 정수 A₁, A₂, ..., Aₙ이 주어진다.
이 중 서로 다른 세 수를 골라 Aᵢ + Aⱼ = Aₖ를 만족하는 경우의 수를 구하라."

여기서 N ≤ 2,000, 그리고 각 Ai는 |Ai| ≤ 1,000,000,000 이다.
처음에는 쓰리 포인터 기반 완전 탐색으로 접근했지만, 성능상의 한계가 있었고
이후 투 포인터 방식으로 리팩토링하면서 성능을 획기적으로 개선할 수 있었다.

🔍 기존 접근: 쓰리 포인터 기반 완전 탐색

N = int(input())
num_lst = list(map(int, input().split()))
num_lst.sort()
left = 0
now = len(num_lst)-2
right = len(num_lst)-1
visited = [0 for _ in range(N+1)]
count = 0

while True:
    if left >= right:
        break
    if now <= left:
        left += 1
        right = len(num_lst)-1
        now = len(num_lst)-2
    for number in range(right, now, -1):
        if num_lst[left] + num_lst[now] < num_lst[number]:
            right -= 1
        if num_lst[left] + num_lst[now] == num_lst[number]:
            if visited[number] == 0:
                visited[number] = 1
                count+=1
    now -= 1
print(count)

• 세 수의 인덱스를 left, now, number로 두고 조합을 확인
• 시간 복잡도는 거의 O(N³) 에 가까우며, N=2,000이면 최대 80억 번까지 돌 수 있다.

🔧 개선: 투 포인터 기반 리팩토링

import sys
input = sys.stdin.readline

N = int(input())
num_lst = list(map(int, input().split()))
num_lst.sort()

count = 0

for i in range(N):
    target = num_lst[i]
    left = 0
    right = N - 1

    while left < right:
        if left == i:
            left += 1
            continue
        if right == i:
            right -= 1
            continue

        total = num_lst[left] + num_lst[right]

        if total == target:
            count += 1
            break
        elif total < target:
            left += 1
        else:
            right -= 1

print(count)

✅ 성능 비교 및 결론

항목	쓰리 포인터	투 포인터
시간 복잡도	O(N³)	O(N²)
최대 연산 횟수	약 80억	약 400만
정렬 필요 여부	필요	필요

📌 정리

• Ai + Aj = Ak 문제는 target을 고정시키고, 나머지를 탐색하는 방식이 효과적이다.
• 정렬 + 투 포인터는 O(N²) 안에서 대부분의 세 수 조건 문제를 해결할 수 있다.