[3273] 두 수의 합

백준 Silver III | 3273 | Python | 문제 링크

---

문제 설명

n개의 서로 다른 양의 정수로 이루어진 수열이 있다. 자연수 x가 주어졌을 때, ai + aj = x (i < j)를 만족하는 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 수열의 원소가 공백으로 구분되어 주어진다. 셋째 줄에는 자연수 x (1 ≤ x ≤ 2,000,000)가 주어진다. 모든 원소는 1보다 크거나 같고 1,000,000보다 작거나 같은 자연수이다.

출력

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

입출력 예

입력	출력
9 5 12 7 10 9 1 2 3 11 13	3

---

나의 풀이

풀이 1 - 투 포인터

import sys
input = sys.stdin.readline

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

nums.sort()

answer = 0
left, right = 0, n-1

while left < right:
    s = nums[left] + nums[right]

    if s == target:
        answer += 1
        left += 1
        right -= 1
    elif s < target:
        left += 1
    else:
        right -= 1

print(answer)

정렬 후 양 끝에서 포인터를 좁혀가며 합을 확인한다. 합이 target과 같으면 양쪽 포인터를 모두 이동하고, 작으면 left를, 크면 right를 이동한다. O(N log N) 으로 해결한다.

풀이 2 - 완전 탐색 (시간 초과)

import sys
input = sys.stdin.readline

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

answer = 0

for i in range(n):
    for j in range(i+1, n):
        if nums[i] + nums[j] == target:
            answer += 1

print(answer)

모든 쌍을 확인하는 O(N²) 풀이다. N이 최대 100,000이므로 최악의 경우 약 50억 번 연산이 필요해 시간 초과가 발생한다.