[ 백준 / 3273 ] 두 수의 합 (Python)

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

 

난이도 : 실버 3 
알고리즘 유형 : 투포인터, 정렬 
풀이 시간 : 12분 

문제 풀이 

구하고자 하는 자연수 $x$가 주어졌을 때, 수열의 $a_{i} + a_{j} = x$를 만족하는 수열 쌍의 개수를 구해보는 문제이다.

 

수열의 크기를 먼저 확인해보면, $n ≤ 100000$으로 주어졌다. 따라서, 조합을 완전탐색으로 풀어본다면, $O(10000C2)$로 약 50억이기 때문에 시간초과가 발생한다. 

 

따라서, 우리는 투포인터 개념을 활용해 이를 해결할 수 있다.

투포인터란, 두 개의 인덱스 번호를 통해 한 배열에서 원하는 수를 접근하기 위한 방법론으로, 1차원 배열의 경우 $O(n)$의 시간복잡도로 문제를 해결할 수 있다.

 

먼저, 투포인터 사용을 위해 먼저 배열을 정렬해주었다. 이후 `left idx`를 `0`, `right idx`를 `n - 1`로 지정해주었다.

이제 left idx가 right idx보다 작은 경우에 대해서만 while문을 돌아줄 것이다. while 문을 돌면서, $a_{i} + a_{j}$를 진행해주고, 만약 값이 x와 같거나 작은 경우, left idx에 +1을 진행해준다. 만약 값이 x보다 큰 경우라면, right의 idx를 -1 해주어 수를 줄여나가는 방법을 통해 시간복잡도 $O(n)$으로 문제를 해결할 수 있다.

 

코드

'''
자연수 x가 주어졌을 때, ai + aj = x를 만족하는 쌍의 수를 구하자

수열의 크기 n <= 100000
'''

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

# 1 2 3 5 7 9 10 11 12
# 정렬 후, 수가 커지면 right idx 줄이고, 수가 작거나 같다면 left idx 옮기기

left, right = 0, n - 1
ans = 0
while left < right:
    total = arr[left] + arr[right]
    if total <= x:
        if total == x:
            ans += 1
        left += 1
    else:
        right -= 1

print(ans)

배운 점 

투포인터 알고리즘에 접근하기 위해서는 여러 문제 풀이 경험을 통해 사례를 익혀야 할 것 같다.

하지만 모든 문제를 풀면서 완전탐색적 사고로 우선 접근하는 것은 잊지 말자 ! (알고리즘 풀이는 거의 항상 완전탐색을 전제로 시작된다!)