문제 링크

바로가기

문제 풀이

PY

import sys
input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))
numbers.sort()

cnt = 0
for idx, number in enumerate(numbers):
  start_idx, end_idx = 0, n - 1

  while start_idx < end_idx:
    sum = numbers[start_idx] + numbers[end_idx]

    if sum == number:
      if start_idx == idx: start_idx += 1
      elif end_idx == idx: end_idx -= 1
      else:
        cnt += 1
        break
    elif sum < number:
      start_idx += 1
    else:
      end_idx -= 1

print(cnt)

풀이

투 포인터 알고리즘을 이용하여 문제를 풀었다.

배열을 입력받은 후에 정렬을 한 뒤, 인덱스를 시작 지점과 끝 지점에 두고 해당 인덱스에서의 숫자 합을 비교한다. 하지만 이때 타겟 인덱스가 두 인덱스와 같으면 안되기 때문에 거기에 대한 분기를 타주었다.

새롭게 배운 점

1. 투포인터 알고리즘을 사용하여 문제를 푼다고 했을 때는 시작 인덱스와 끝 인덱스를 시작으로 인덱스를 바꿔가면서 수를 비교해야하기 때문에 배열이 정렬되어있어야한다.