[python/파이썬] 백준 3273 sumX

[문제 출처] 

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

3273번: 두 수의 합

 

[문제 풀이]

투 포인터로 풀 수 있는 문제이다.

이중 for문을 돌리면 시간초과가 나온다.

 

우선 수열을 오름차순으로 정렬한 후에 좌측과 우측 끝을 나타내는 변수 left, right를 선언한다.

그 후에 두 변수가 가운데에서 만나 어긋나기 전까지 계속해서 진행하면 되는데,

만일 left에 위치한 수와 right에 위치한 수의 합이 x와 같아지면 cnt값을 증가시키고,

left를 증가시키거나, right를 감소시켜서 합을 x와 달라지게 한다.

오름차순으로 정렬이 되어있기에 x보다 합이 작을 때는 left를 증가시키고, 클 때는 right를 감소시킨다.

#3273

n = int(input())
arr = list(map(int, input().split()))
x = int(input())
cnt = 0

arr.sort()
left = 0
right = n-1
while left < right:
  if arr[left] + arr[right] == x :
    right -= 1
    cnt += 1
  elif arr[left] + arr[right] < x:
    left += 1
  else:
    right -= 1

print(cnt)