[백준] 3273 두 수의 합

문제

• n개의 서로 다른 양의 정수 $a_1, a_2, .., a_n$ 이 있을 때, $a_i + a_j = x$를 만족하는 $(a_i, a_j)$ 쌍의 개수 구하기
  • 1 <= n <= 100,000
  • 1 <= x <= 2,000,000

 

풀이

• 시간 복잡도 : N이 10만이므로 $O(N^2)$ 안된다.
• 정렬하고 투 포인터로 (앞 + 뒤) 가 X인지 확인
  • 크면 뒤 포인터를 앞으로 옮기고,
  • 작으면 앞 포인터를 앞으로 옮기면서 비교하기
• 동일한 숫자가 여러 개 존재할 수 있으므로, Counter 이용해 숫자 개수를 세놓고 쌍의 개수 구하기 

 

from collections import Counter
N = int(input())
numbers = list(map(int, input().split()))
X = int(input())

num_cnt = Counter(numbers)              # 숫자별 개수 세기
numbers = sorted(list(num_cnt.keys()))  # 각 숫자 정렬하기
s, e = 0, len(numbers)-1
answer = 0
while s < e:
    summation = numbers[s] + numbers[e]
    if  summation == X :                # 숫자의 합이 X 일때
        answer += num_cnt[numbers[s]] * num_cnt[numbers[e]]
        s += 1
        e -= 1
        
    elif summation > X :                # 숫자의 합이 X보다 클 때
        e -= 1                              # 뒷포인터 -1
    else:                               # 숫자의 합이 X보다 작을 때
        s += 1                              # 앞포인터 +1

print(answer)

 

 

 

References

• 백준 3273번
• 2023.05.05 오늘의 문제