알고리즘 - Python / 백준 - 3273번 : 두 수의 합

3273번: 두 수의 합 (acmicpc.net)

3273번: 두 수의 합

 

---

풀이

• 수열 중 ai + aj = x 를 만족하는 쌍의 개수를 찾는 문제다.
• 투 포인터로 풀 수 있는 가장 기본적인 문제다.
• 수열을 정렬한 후 앞과 뒤 부터 포인터를 출발시켜 , x보다 크다면 뒤쪽을 당겨 합을 줄이고 x보다 작다면 앞쪽을 밀어 합을 늘인다.
• 두 포인터가 만날 때 , while 문이 종료되도록 하면 모든 범위에 대해 투 포인터들이 합을 검사하고 이를 통해 정답을 찾을 수 있다.

 

import sys
n = int(sys.stdin.readline())
s = list(map(int , sys.stdin.readline().split(" ")))
x = int(sys.stdin.readline())
s.sort()

fp=0; ep=len(s)-1; ans = 0
while fp != ep:
    if s[fp] + s[ep] == x:
        ep -= 1
        ans += 1
    else:
        if s[fp] + s[ep] < x:
            fp += 1
        else:
            ep -= 1
print(ans)

---