백준 3273번: 두 수의 합 [python]

https://www.acmicpc.net/problem/3273

---

문제 접근

"투 포인터" 라는 유형의 문제이다.

‘투 포인터(Two Pointer)’는 정렬된 배열에서 두 개의 포인터를 움직이며 효율적으로 값을 찾는 기법이다. 보통 O(N²) 시간이 드는 걸 O(N) 또는 O(N log N)으로 줄일 수 있어서 코딩테스트 단골 패턴이라고 한다.

핵심 개념

• 정렬된 배열에서 두 개의 인덱스(pointer)를 조절하며 원하는 조건을 만족하는 쌍 또는 부분 구간을 찾는다.
• 포인터 두 개를 쓰기 때문에 이름이 Two Pointer.

해답 및 풀이

import sys
input = sys.stdin.readline

# 입력
n = int(input()) # 수열 개수
a_list = list(map(int,input().split())) # 수열
x = int(input()) # 목표 숫자
answer = 0 # 답 ( 쌍의 개수 )
checked = set() # 지금까지 본 숫자 저장용

# answer 구하는 로직

# 수열을 순회할건데 (x - 요소)가 존재하면 answer 의 cnt를 하나 증가시키기.
for a in a_list:
    if x-a in checked:
        answer += 1 
    checked.add(a)

print(answer)

어떤 수 a를 보면서, 그 수 a 이전에 등장한 수들 중에 x - a가 있었는가? 를 확인하여 있으면 answer를 + 해주었다.
set을 써서 탐색을 빠르게 만들고, 중복 쌍은 생성되지 않도록 현재 수 a는 그 이후 쌍을 만들기 위해 기록만 해둠

---

통과는 되지만 투 포인터 방식은 아니었다.

투 포인터 방식을 이용한 코드

import sys
input = sys.stdin.readline

# 입력
n = int(input()) # 수열 개수
a_list = list(map(int,input().split())) # 수열
x = int(input()) # 목표 숫자

a_list.sort() # 투 포인터는 정렬이 필수이다.

answer = 0 # 답 ( 쌍의 개수 )

left = 0
right = n - 1

# 두 포인터가 교차하기 전까지 반복
while left < right:
    total = a_list[left] + a_list[right]
    if total == x: # 합이 x와 같다면
        answer += 1 # 정답 개수 증가
        left += 1 # 왼쪽 포인터 오른쪽으로 이동
        right -= 1 # 오른쪽 포인터 왼쪽으로 이동
    elif total < x: # 합이 x보다 작다면
        left += 1 # 더 큰 수를 만들기 위해 왼쪽 포인터만 오른쪽으로 이동
    else: # 합이 x 보다 크다면
        right -= 1 # 더 작은 수를 만들기 위해 오른쪽 포인터 이동

print(answer)

left, right 라는 포인터 (index를 통해) 만들어주고
그 두개의 포인터의 합을 total로, 그리고 그것을 타겟 넘버인 x와 비교하며
포인터의 인덱스를 조정해가며 answer의 카운트를 늘려주는 방식이었다.

이 방식이 뭔가 더 직관적이고 마음에 든다.