[Silver III] 두 수의 합 - 3273

[Silver III] 두 수의 합 - 3273

문제 링크

성능 요약

메모리: 128904 KB, 시간: 3764 ms

분류

정렬(sorting), 두 포인터(two_pointer)

문제 설명

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)

출력

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

import sys
input = sys.stdin.readline
n = int(input())
array = sorted(list(map(int,input().split())))
x = int(input())
cnt = 0
if len(array) == 1:
  print(cnt)
else:
  for i in range(len(array)-1):
    for j in range(i+1,len(array)):
      if array[i]+array[j] > x:
        break
      elif array[i]+array[j] == x:
        cnt += 1
        break
  print(cnt)

풀고보니 투 포인터 문제였다. N의 범위가 100000이라서 그냥 반복문을 쓰지 않을까 하다가,,두 수를 더한 값이 x보다 클 경우 break를 걸면 복잡도가 덜 하지 않을까 싶어서 시도해봤는데 정답 문구가 떴다.

그러나, 이 문제에서 원하는 알고리즘은 투 포인터였던 것 같다.

-두 포인터

left = 0 , right = n-1로 잡아서

1. 두 수의 합이 x보다 큰 경우 - 더 큰 값을 더해야하므로 left+1
2. 두 수의 합이 x보다 작은 경우 - 더 작은 값을 더해야하므로 right-1
3. 두 수의 합이 x인 경우 - answer+1 & left+1

#투 포인터 풀이 출처 : https://velog.io/@djagmlrhks3/Algorithm-BaekJoon-3273.-%EB%91%90-%EC%88%98%EC%9D%98-%ED%95%A9-by-Python