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

3273 두 수의 합

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

문제

n개의 서로다른 양의 정수 로 이루어진 수열이 있다 ai의 값은 1보다 크고 1000000보다 작거나 같은 자연수

자연수 x 가 주어질때 ai+aj=x 를 만족하면 (ai,aj)쌍의 수를 구하는 프로그램을 작성하시

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다.

출력

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

 

풀이

처음 풀었을때에는 완전탐색으로 풀었다 그랬더니 시간초과가 나서  알고리즘 유형을 보니 투 포인터 였다투 포인터가 2개의 위치 좌표를 이용하여 빠르게 합을 구하는 방법 인데 문제 내용을 보니 투 포인터 보다는 이진 탐색에 가까운 풀이 방식인것 같다는 생각을 했다 left =0 right=리스트의 길이-1 로 지정하고 주어진 배열을 정렬로 돌리고 난후 while left<right  조건으로 while 문을 돌린다두수의 합은 주어진 수와 같으며 쌍의 개수를 저장한 변수의 값을 증가시키고 right값을 -1 감소시킨다두수의 합이 주어진 수보다 작으면 left 값을 +1을 증가시킨다두수의 합이 주어진수보다 크면 right -1하여 값을 감소시키면서 쌍의 수를 찾을수 있다 다른 조건을 생각할 필요가 없는 이유는 조건에 서로다른 양의 정수라고 명시 되어 있기 때문이다

코드

n=int(input())
array=list(map(int, input().split()))
x=int(input())
count=0
array.sort()

left=0
right=n-1

while left<right:
    sum=array[left]+array[right]
    if sum==x:
        count+=1
        right-=1
    if sum>x:
        right-=1
    elif sum<x:
        left+=1

print(count)