[백준] 3273번: 두 수의 합 (파이썬)

✅문제: 3273번

3273번: 두 수의 합

📌개념정리

(1) 투 포인터(Two Pointers)

• 정의: 배열이나 리스트에서 두 개의 포인터를 이용하여 문제를 해결하는 기법
• 보통 정렬된 배열에서 두 요소의 합, 차 등을 계산할 때 사용함.
• 이 문제에서는 left, right 두 포인터를 이용하여 합이 특정 값 X와 일치하는 쌍을 찾음.

📌문제풀이

이 문제는 주어진 수열에서 두 수의 합이 특정 값 X와 같아지는 경우의 수를 찾는 문제임.

 

먼저, 파이썬 코드를 어떻게 작성할지 로직을 고민함.

1. 주어진 수열을 오름차순으로 정렬
2. 수열의 양 끝에서 시작하여 중간으로 이동하면서 두 수의 합을 X와 비교
3. 합이 X와 일치할 경우, 카운트를 증가시키고 양 포인터를 동시에 움직여 다른 쌍을 찾음
4. 합이 X보다 작으면 왼쪽 포인터를 오른쪽으로, X보다 크면 오른쪽 포인터를 왼쪽으로 이동하여 합을 조절
5. 포인터가 서로 교차할 때까지 반복

n = int(input())  # 수열의 크기
numbers = list(map(int, input().split()))  # 수열
x = int(input())  # 목표 합 X

numbers.sort()

count = 0  # X와 같아지는 경우의 수
left, right = 0, n-1

while left < right:
    current_sum = numbers[left] + numbers[right]
    if current_sum == x:  # 합이 X와 같으면
        count += 1
        left += 1
        right -= 1
    elif current_sum < x:  # 합이 X보다 작으면
        left += 1
    else:  # 합이 X보다 크면
        right -= 1

print(count)

1. 수열의 크기 n, 수열의 원소들, 그리고 목표 합 X를 입력받음.
2. 수열을 오름차순으로 정렬함.
3. 두 개의 포인터 left와 right를 수열의 시작점과 끝점에 위치시킴.
4. 현재 두 포인터가 가리키는 원소의 합을 계산하고 X와 비교함.
   1. 합이 X와 같다면, count를 하나 증가시키고, left는 오른쪽으로, `right`는 왼쪽으로 움직여 다음 가능한 쌍을 찾음.
   2. 합이 X보다 작으면, left 포인터를 오른쪽으로 이동시켜 합을 증가시킴.
   3. 합이 X보다 크면, right 포인터를 왼쪽으로 이동시켜 합을 감소시킴.

📌후기

• 투 포인터 기법을 활용하여 O(n log n)의 시간 복잡도(정렬 포함)로 효율적으로 해결할 수 있는 것 같음. 수열이 이미 정렬되어 있다면 O(n) 시간에 해결 가능함.
• 처음에는 해시맵을 고려했었지만, 정렬과 투 포인터를 사용하는 것이 더 직관적이고 빠르게 문제를 해결할 수 있었음.

📌참고자료

1) _rian, "[Algorithm] 투포인터(Two Pointer) 알고리즘", 2021.04.28, https://butter-shower.tistory.com/226