[🥈3 / 백준 3273 / 파이썬] 두 수의 합

 

3273번: 두 수의 합

 

문제

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

입력

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

출력

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

 

예제 입력  9 5 12 7 10 9 1 2 3 11 13

예제 출력  3

 

풀이

 

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

 

이중 for문을 이용할 경우 100,000 * 100,000의 연산을 요구하기 때문에 TLE가 뜰 것이다.

따라서 투 포인터를 이용하여 양쪽에서 포인터를 좁혀오며 두 수의 쌍이 x를 만족할 경우를 구해야 한다.

 

원리는 간단하다. 오름차순으로 정렬된 배열에서 i는 그 배열의 최솟값, j는 최댓값을 가르킬 것이다.

만약, a[i] + a[j] 가 x보다 크다면, 최댓값을 줄이면 된다. 즉, j라는 포인터를 1 감소시키며 다음 수를 비교한다.

만약 x보다 작다면, 반대로 최솟값 포인터를 올리면 된다.

 

두 수의 합이므로 i == j 가 된다면 두 수의 비교가 아니게 되므로 코드를 종료한다.

 

import sys
input = sys.stdin.readline

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

i=0;j=n-1;cnt=0
while(True):
    if a[i]+a[j] == x:
        cnt+=1 
    
    # <= 여도 결과는 같다.
    if a[i] + a[j] < x:
        i+=1
    else:
        j-=1
    if i >= j:
        break
print(cnt)