[BOJ/Python] 3273_두 수의 합

문제 출처:https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

문제

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)

출력

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

예제 입력 1

9
5 12 7 10 9 1 2 3 11
13

예제 출력 1

3

---

풀이

 

투 포인터를 이용하는 문제이다.

투 포인터에 대한 설명은 아래 게시물에 작성해 두었다.

투 포인터(Two Pointers) 알고리즘

 

만약 이 문제를 반복문을 이용하여 푼다면 n개의 수 각각에 대하여 나머지 수와의 합을 구하여 그 값이 x와 같은지 비교해야 하므로 O(n**2)의 시간 복잡도가 나오게 된다.

하지만 투 포인터를 이용하게 되면 우선 리스트를 정렬해야 하므로 O(nlogn)의 시간 복잡도가 나오게 되고, 탐색의 경우 O(n)의 시간 복잡도로 총 O(nlogn)의 시간복잡도로 문제를 해결할 수 있다.

• 우선 투 포인터를 이용하기 위해 리스트를 오름차순으로 정렬한다.
• start 포인터(파란색 포인터)는 0번 index의 값을 가리키고, end 포인터(빨간색 포인터)는 n-1 번째 index의 값을 가리킨다.
• 두 수의 합(sum)을 찾아야 하는 값인 x와 비교한다.
• 두 수의 합이 x보다 크므로, end 포인터를 한 칸 왼쪽으로 이동시킨다. ( 두 수의 합을 감소시켜야 하기 때문이다.)

 

• 마찬가지로 두 수의 합과 x를 비교한다.
• 여기서도 두 수의 합이 x보다 크므로, end 포인터를 한 칸 왼쪽으로 이동시킨다.

• 두 수의 합이 x와 같으므로 count를 1 증가시킨다.(쌍의 개수를 출력해야 하기 때문에 count를 구한다.)
• 그리고 여기서 주어진 양의 정수는 모두 서로 다른 값이기 때문에 각각의 포인터를 한 칸씩 이동시킨다.
• (또 다른 1과 12가 존재하지 않으므로 두 포인터가 가리키는 각각의 값과의 합이 x가 되는 경우는 더 이상 존재하지 않는다.)

 

• 두 수의 합이 x보다 작으므로 start 포인터를 한 칸 오른쪽으로 이동시킨다. ( 두 수의 합을 증가시켜야 하기 때문이다.)

 

• 두 수의 합이 x이므로 count를 1 증가시키고 두 포인터를 한 칸씩 이동시킨다.

 

 

• 마찬가지로 두 수의 합이 x이므로 count를 1 증가시키고, 두 포인터를 한 칸씩 이동시킨다.
• 여기서 두 포인터가 이동하게 되면 두 포인터가 교차하게 되므로 탐색을 종료한다.
• 최종적으로 합이 x가 되는 쌍의 개수인 count를 출력한다. (이 경우 3이다.)

 

코드는 다음과 같다.

 

import sys
n = int(sys.stdin.readline())
n_list = list(map(int,sys.stdin.readline().split()))
x = int(sys.stdin.readline())
 
n_list.sort()
 
start = 0
end = n-1
count = 0
 
for start in range(n):
    while start<end and n_list[start] + n_list[end] > x:
        end-=1
 
    if start>=end:
        break
    
    if n_list[start] + n_list[end] == x:
        count+=1
        end-=1
 
print(count)