[백준] 3273번 두 수의 합 해설 및 풀이 (Python)

백준 3273번 두 수의 합

 

https://www.acmicpc.net/problem/3273

 

---

 

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

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

 

---

 

문제 풀이

 

문제 유형

정렬

두 포인터

 

 

풀이 도출 과정

1. 주어진 수열에서 두 개의 수를 선택하여 합이 x가 되는 쌍의 개수를 찾는 문제입니다.
2. 따라서 투 포인터를 사용하기 위해 정렬합니다.
3. 왼쪽 포인터(left), 오른쪽 포인터(right)를 활용해 합이 x가 되는 쌍을 탐색합니다.
4. 만약 nums[left] + nums[right] == x이면 쌍을 찾은 것이므로 카운트 증가 후 포인터를 이동시킵니다.
5. nums[left] + nums[right] < x이면 합을 증가시키기 위해 left 이동시킵니다.
6. nums[left] + nums[right] > x이면 합을 감소시키기 위해 right 이동시킵니다.

 

시간 복잡도

• 정렬: O(n log n)
• 투 포인터 탐색: O(n)
• 총 시간 복잡도: O(n log n)

 

※ 브루트포스 방식 O(n²)은 n ≤ 100,000일 때 시간 초과 가능성이 있습니다.

 

---

 

문제 풀이 코드

 

처음에 작성한 코드

import sys

# 수열의 크기 n 입력
n = int(sys.stdin.readline())

# 수열의 원소들을 리스트로 저장
nums = list(map(int, sys.stdin.readline().split()))

# 목표 합 x 입력
x = int(sys.stdin.readline())

# 쌍의 개수를 저장할 변수
count = 0

# 수열을 오름차순 정렬
nums.sort()

for i in range(n - 1):
    left = i + 1  # 왼쪽 포인터
    right = n - 1  # 오른쪽 포인터

    while left < right:
        current_sum = nums[i] + nums[left] + nums[right]

        if current_sum == x:  # 목표값과 같다면 카운트 증가
            count += 1
            left += 1  # 중복 방지를 위해 다음 숫자로 이동
            right -= 1  # 중복 방지를 위해 다음 숫자로 이동
        elif current_sum < x:  # 합이 부족하면 왼쪽 포인터 증가
            left += 1
        else:  # 합이 초과하면 오른쪽 포인터 감소
            right -= 1


# 결과 출력
print(count)

 

위 코드는 두 개의 숫자가 아니라 세 개의 숫자의 합을 비교하는 방식 (current_sum = nums[i] + nums[left] + nums[right])을 사용하고 있었습니다.

 

하지만 문제에서는 두 개의 숫자 합이 x가 되는 경우의 수를 구해야 합니다.

 

 

따라서 제출 시 시간 초과가 (당연히) 뜹니다.

 

 

수정된 코드

 

처음에 작성한 코드에서는 i를 고정시켰었는데, 그럴 필요 없이 투 포인터의 left, right으로 해결이 가능하게 변경하였습니다.

 

import sys

input = sys.stdin.readline

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

nums.sort()  # 정렬
left, right = 0, n - 1  # 투 포인터 초기화
count = 0

while left < right:
    current_sum = nums[left] + nums[right]
    
    if current_sum == x:  # 합이 x인 경우
        count += 1
        left += 1
        right -= 1
    elif current_sum < x:  # 합이 x보다 작으면 left 이동
        left += 1
    else:  # 합이 x보다 크면 right 이동
        right -= 1


print(count)

 

---

투 포인터 vs 이분 탐색 개념 정리

 

투 포인터(Two Pointer)

 

개념:

• 두 개의 포인터(left, right)를 사용하여 배열을 탐색하는 방식.
• 정렬된 배열에서 특정 조건을 만족하는 값을 빠르게 찾을 때 유용.
• 포인터를 조절하면서 값을 비교하는 방식.

 

사용 예시

• 두 수의 합 문제 (두 개의 수를 더해서 특정 값을 찾는 경우)
• 구간 합 문제 (연속된 부분 수열의 합이 특정 조건을 만족하는 경우)
• 투 포인터를 활용한 최적화 문제 (예: 중복 제거, 정렬된 배열의 차이 최소화 등)

 

이분 탐색(Binary Search)

 

개념:

• 정렬된 배열에서 특정 값을 찾는 방법으로, 매번 탐색 범위를 절반으로 줄여가면서 찾음.
• O(log n)
• 한 번의 비교에서 전체 범위를 절반으로 줄이므로 검색 속도가 빠르다.

 

사용 예시

• 정렬된 배열에서 특정 값 찾기 (정확한 값이 있는지 확인)
• 최적화 문제 (예: Parametric Search, Lower/Upper Bound)
• 목표 값과 가장 가까운 값 찾기
• 이진 탐색을 활용한 최적화 문제 (예: LIS(최장 증가 부분 수열), 매개 변수 탐색 등)