1 minute read

문제

접근 방법

모든 가능한 짝의 합을 구하기엔 데이터 개수가 너무 많아서 시간 초과가 날 것이 뻔하다. O(N)으로 해결하기 위해서는 각 수를 set에 저장하고 target x에서 각 수를 뺀 수가 set에 존재하는지 확인하는 방법을 사용해야 한다.

정답 코드 1 (O(N))


import sys
input = sys.stdin.readline

"""
모든 가능한 짝의 합을 구해서 x가 되는지 확인하려면 N^2의 시간이 필요하다. 
O(N)으로 x가 되는 짝이 존재하는지 구하기 위해서는 각 수를 set에 저장하고 x에서 각 수를 뺀 수가 set에 존재하는지 확인
"""

n = int(input())

nums = list(map(int, input().split()))

x = int(input())

# nums를 set로
exist = set()

#이미 짝을 이룬 애들
already_paired = set()


for num in nums:
  exist.add(num)

num_pairs = 0

for a_1 in nums:
  a_2 = x - a_1
  # 합치면 x를 이룰 수 있는 수가 nums에 존재하는지, a_1과 a_2가 같은 숫자는 아닌지, 그리고 이미 짝을 이룬 수가 아닌지 확인
  if a_2 in exist and a_1 != a_2 and a_2 not in already_paired:
    num_pairs +=1
    already_paired.add(a_1)
    already_paired.add(a_2)

print(num_pairs)

정답 코드 2 (두 포인터)

O(N^2)의 경우의 수를 특별한 환경에서는 O(N)으로 iterate 할 수 있는 방법이 존재한다.

$\rightarrow$ 두 포인터이다. 숫자들을 정렬을 하면 한 수에서 다른 수가 멀어질수록 합이 커지는 규칙을 통해 투 포인터로 모든 가능한 짝들을 관찰할 수 있게 된다.

두 포인터를 통해 시작점과 맨 끝의 합이 x보다 작다면 합을 키우기 위해 시작점을 오른쪽으로, 합이 x보다 크다면 합을 줄이기 위해 끝 점을 왼쪽으로, 합이 x와 같다면 추가하고 다른 경우의 수를 보는 것이다. 이때 다른 경우의 수를 보기 위해 시작점을 옮기는 이유는 끝점을 옮겨봤자 합이 작아지기 때문에 시작점을 바꿔야 다른 가능한 짝 경우에 수를 볼 수 있기 때문이다.

import sys
input = sys.stdin.readline


n = int(input())

nums = list(map(int, input().split()))
nums.sort()

x = int(input())

ans = 0

start = 0
end = n-1

while start<end:
  if nums[start]+nums[end] < x:
    start+=1
  elif nums[start]+nums[end] > x:
    end -=1
  else:
    ans+=1
    start+=1

print(ans)

You May Also Enjoy