[알고리즘] 백준 3273 파이썬 - 두 수의 합

 

3273번: 두 수의 합

문제

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

 

문제풀이

import sys
input = sys.stdin.readline
#01
n=int(input())
arr=list(map(int,input().split()))
x=int(input())
arr.sort()
#02
left,right=0,n-1
ans=0

#03
while left<right:
    tmp=arr[left]+arr[right]
    if tmp==x: ans+=1
    if tmp<x:
        left+=1
        continue
    right-=1
#04
print(ans)

- 두 포인터를 사용해서 문제를 풀었다.

- #01 : 해당 문제에서 주어진 입력들을 각각 저장해준다. 이후 ans를 오름차순 정렬해준다.

- #02 : 두 포인터를 이용하여 시작값을 각각 처음과 끝으로 지정해준다.

- #03 : tmp값이 x와 같으면 정답(ans)를 1 늘려준다.

           tmp값이 x보다 작으면 left 값을 1 늘려준다. -> 즉 tmp 값이 점점 커짐

          위의 if문 2개를 모두 통과하면 right를 1 감소시킨다.

          즉 해당 right에 적합한 left값을 모두 사용하였기에 새로운 right로 변경한다.

          left의 값이 right보다 같거나 커지면 while문을 종료한다.

- #04 : 위에서 구한 ans 값을 출력한다.