[백준/Python] 3273. 두 수의 합 (투포인터) 🥈3️⃣

---

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

예제 입력

9
5 12 7 10 9 1 2 3 11
13

예제 출력

3

---

풀이

1. 문제의 핵심 이해하기

이 문제는 정수 배열에서 두 수를 골라서 합이 $x$가 되는 쌍의 개수를 구하는 문제이다.

처음 떠올리기 쉬운 방법은 모든 두 수를 다 확인하는 것이다.
구현하기엔 쉽겠지만, 시간복잡도가 O(N²) 이라서 비효율적이다.
따라서, 정렬 + 투포인터를 사용해 풀어야 한다.

2. 투포인터(Two Pointers)란?

배열을 정렬한 뒤, 왼쪽 끝을 left, 오른쪽 끝을 right라고 두 개의 손가락(포인터)을 둔다. 양 끝 지점에서 가운데로 한쪽 포인터를 조건에 따라 이동시키며 탐색 범위를 줄여가는 방식이다.

준비물: 정렬된 숫자 배열 (중요! 반드시 오름차순 정렬이 되어 있어야 한다.)
시작 위치:

• 왼쪽 포인터 ($left$): 배열의 맨 첫 번째 (가장 작은 값)
• 오른쪽 포인터 ($right$): 배열의 맨 마지막 (가장 큰 값)

💡 투 포인터를 쉽게 이해하기

배열을 정렬한 뒤,
왼쪽 끝을 left, 오른쪽 끝을 right 라고 두고 시작한다.

예를 들어 정렬된 배열이
[1, 2, 3, 4, 5, 7] 이고, 목표 합이 8이라면

• left = 0 → 1
• right = 5 → 7

1️⃣ 1단계
1 + 7 = 8 찾았다. 개수 1 증가.

그다음엔 같은 쌍을 또 세면 안 되니까
left += 1, right -= 1

2️⃣ 2단계
이제 2 + 5 = 7. 목표보다 작다.

그러면 더 큰 수가 필요하니까 왼쪽 값을 키워야 한다.
즉, left += 1

3️⃣ 3단계
3 + 5 = 8. 또 찾았다. 개수 1 증가.

다시 left += 1, right -= 1
이제 left >= right가 되면 종료.

왜 이렇게 움직이는걸까?

현재 합이 x보다 작다는 건, 더 큰 수가 필요하다는 뜻이다.

정렬되어 있으니까

• 오른쪽은 이미 큰 값
• 왼쪽을 오른쪽으로 옮기면 값이 커짐

그래서 left를 증가시켜야 한다.

현재 합이 x보다 크다는 건, 더 작은 수가 필요하다는 뜻이다.

정렬되어 있으니까

• 오른쪽을 왼쪽으로 옮기면 값이 작아짐

그래서 right를 감소시켜야 한다.

이제 이 내용을 바탕으로 알고리즘을 정리해보면 다음과 같다.

🧠 최종 알고리즘

1. 수열을 입력받는다
2. 정렬한다
3. left = 0, right = n - 1로 시작한다
4. left < right 동안 반복한다
	5. 두 수의 합을 보고
	6. x와 같으면 count 증가 후 양쪽 이동
	7. x보다 작으면 left 증가
	8. x보다 크면 right 감소

---

코드

코드로 구현한다면 아래와 같다.

n = int(input())
arr = list(map(int, input().split()))
x = int(input())

arr.sort()

left = 0
right = n - 1
count = 0

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

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

print(count)