BoJ 9728 - Pair Sum [with Python / 문제 한국어로 번역]

📍 문제

문제

크기가 $N$인 정수 배열과 정수 $M$이 주어집니다.
이 배열에는 $(N*(N-1))/2$개의 서로 다른 쌍이 있습니다.
이 중에서 합이 $M$과 같은 쌍의 수를 계산해야 합니다.
예를 들어, 배열이 {1, 2, 3, 4}이고 $M$이 5이면,
합이 $M$과 같은 정확히 2개의 쌍 {1, 4}과 {2, 3}이 있습니다.

입력

첫 번째 줄에는 $T$라는 양의 정수가 주어지며, $T$는 100,000 이하입니다. 이후 각 테스트 케이스에 대한 입력이 나옵니다.

각 테스트 케이스는 두 줄로 구성됩니다.
첫 번째 줄에는 공백으로 구분된 2개의 정수 $N$과 $M$이 주어집니다. $N$은 2부터 20,000까지의 값이며, 두 번째 줄에는 $N$개의 정수가 공백으로 구분되어 주어집니다.
이 정수들은 1부터 1,000,000,000까지의 범위에 속하며, 증가하는 순서로 정렬되어 있습니다.
또한 모든 숫자는 서로 다릅니다.

출력

각 테스트 케이스에 대해 출력은 "Case #x: R" 형식의 한 줄로 이루어집니다. 여기서 $x$는 케이스 번호를 나타내며 1부터 시작하며, $R$은 주어진 $M$과 정확히 일치하는 쌍의 수입니다.

📍 아이디어

사실, 아이디어라고 할 것도 없는 정말 basic한 two pointer 문제.
심지어 이미 입력 받을 때 정렬이 되어 있는 상태로 와서
따로 정렬을 해줄 필요도 없다!

그냥 입력을 리스트로 받은 후, start와 end 지정해서
두 합이 기준 값보다 크면 end를 감소시키고 작으면 start를 증가시키고, 같으면 start와 cnt를 증가시키면 끝!

📍 제출 코드

import sys

t = int(sys.stdin.readline().rstrip())

for i in range(t):
  n, m = map(int, sys.stdin.readline().rstrip().split())

  nums = list(map(int, sys.stdin.readline().rstrip().split()))
  start = 0
  end = len(nums)-1
  cnt = 0

  while start < end:
    if nums[start] + nums[end] == m:
      cnt += 1
      start += 1
    if nums[start] + nums[end] > m:
      end -= 1
    if nums[start] + nums[end] < m:
      start += 1
  
  print("Case #%d: %d" %(i+1, cnt))