문제 출처 : https://www.acmicpc.net/problem/3273
난이도 : 실버 3
문제 파악
수열이 하나 주어지고, 그 안에서 서로 다른 두 수의 합이 X가 되는 쌍의 개수를 구하는 문제다.
가장 단순하게 생각하면 모든 쌍을 다 확인하는 O(N²) 풀이가 떠오르지만,
N의 범위를 보면 이 방식은 시간 초과가 난다.
따라서 더 빠른 탐색 방법이 필요하고,
이 문제는 정렬 + 투 포인터로 해결할 수 있는 전형적인 유형이다.
투 포인터란?
투 포인터(Two Pointers)는
배열에서 두 개의 인덱스를 동시에 움직이며 조건을 만족하는 값을 찾는 기법이다.
핵심
포인터를 한 번씩만 이동시켜
전체 배열을 O(N)에 훑는다
불필요한 중복 탐색을 하지 않도록 “이미 확인한 구간은 다시 보지 않는다”는 점이 가장 큰 특징이다.
코테에서 언제 투 포인터를 떠올려야 할까?
문제를 풀다가 아래와 같은 키워드가 보이면 투 포인터를 한 번 의심해보는 게 좋다.
- 두 수 / 두 원소의 합
- 조건을 만족하는 쌍(pair)
- 연속된 구간 / 부분 배열
- 정렬 후 탐색해도 되는 문제
- O(N²)는 안 될 것 같은 입력 크기
특히
“두 수의 합이 X가 되는 쌍의 개수”
이 문장은 거의 투 포인터 시그널에 가깝다.
3273번은
정렬만 해두면 값의 크고 작음을 기준으로 포인터를 움직일 수 있기 때문에
투 포인터를 쓰기에 매우 좋은 문제다.
투 포인터 기본 로직
가장 대표적인 투 포인터 패턴은 다음 흐름을 따른다.
-
배열을 정렬한다
값의 대소 비교가 가능해진다. -
포인터를 양 끝에 둔다
- 하나는 가장 작은 값
- 하나는 가장 큰 값
-
두 값의 합을 확인한다
합이 목표값보다 작으면 → 작은 쪽 포인터 이동
합이 목표값보다 크면 → 큰 쪽 포인터 이동
합이 목표값과 같으면 → 정답 처리 후 양쪽 포인터 이동 -
두 포인터가 만나기 전까지 반복한다.
이 방식의 장점은
각 포인터가 한 방향으로만 이동하기 때문에
전체 시간복잡도가 O(N)으로 끝난다는 점이다.
해답 및 풀이
import sys
input = sys.stdin.readline
# 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수
N = int(input())
nums = list(map(int,input().split()))
target = int(input())
#자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성
# 정렬
nums.sort()
left = 0
right = N-1
count = 0
while left < right:
total = nums[left] + nums[right]
if total > target:
right -= 1
elif total < target:
left += 1
else:
count += 1
left += 1
right -= 1
print(count)그런데 투포인터를 공부하다보니 저번에 접했던 이분 탐색과 공통점이 있어보인다.
이분 탐색이란
이분 탐색(Binary Search)은
정렬된 배열에서 원하는 값을 빠르게 찾기 위해 탐색 범위를 절반씩 줄여가는 알고리즘이다.
가장 큰 특징은 이거다.
매 탐색마다 절반을 버린다
그래서 시간복잡도가 O(log N)이다
대신 조건이 하나 있다.
정렬되어 있어야 한다.
(혹은 정렬된 상태라고 가정할 수 있어야 한다)
보통 이분 탐색은
“이 값이 있나?”, “이 조건을 만족하는 최소/최대 값은 어디까지인가?”
같은 문제에서 사용된다.
투 포인터와 차이점
투 포인터랑 이분 탐색이 꽤 비슷해 보였다.
둘 다 정렬된 배열을 쓰고, 범위를 줄여나가기 때문이다.
그러나 차이점을 알 수 있어야 한다.
투 포인터
- 두 개의 인덱스를 동시에 움직인다
- 쌍(pair)이나 구간을 다룬다
- 두 값의 관계(합, 차, 조건)가 중요하다
- 전체를 한 번 훑는 구조 → O(N)
이분 탐색
- 중간값(mid)을 기준으로 한쪽 절반을 통째로 버린다
- 하나의 값 또는 경계를 찾는다
- 조건이 단조적으로 변해야 한다
- 탐색 범위를 반씩 줄임 → O(log N)
언제 이분 탐색, 언제 투 포인터를 써야 할까
이분 탐색을 떠올려야 할 때
- 정답이 숫자 하나다
- 최댓값 / 최솟값을 구하는 문제
- “이 값이 가능한가?”라는 질문으로 바꿀 수 있다
- 조건이 True → False 또는 False → True로 단조롭게 변한다
투 포인터를 떠올려야 할 때
- 두 수의 합 / 차 / 곱
- 조건을 만족하는 쌍의 개수
- 연속된 부분 배열(슬라이딩 윈도우 포함)
- 정렬 후 값의 크고 작음으로 방향을 정할 수 있을 때
