(BOJ)-3273, Python

문제 요약

출처: (BOJ)3273 - 두 수의 합

길이가 $N$인 수열이 주어질 때, 수열에서 두 원소 $a_i, a_j$​의 합이 $X$가 되는 쌍$(a_i, a_j)$의 개수를 찾는 문제이다.

$1 \le a_i \le 1000000$
$1 \le X \le 2000000$

접근 과정

1. 완전탐색 접근(반복문)

경우를 쪼개서 접근할 문제가 아니라고 판단했기 때문에, 재귀 대신 단순 반복문을 사용하여 모든 가능한 쌍을 구하려고 했다. 결과는 시간 초과였다.

시도한 코드

N = int(input())
arr = list(map(int, input().split()))
X = int(input())
check = [0 for _ in range(N)]

answer = 0
for i in range(N):
    for j in range(N):
        if i == j or check[i] == 1 or check[j] == 1: 
            continue
        if arr[i] + arr[j] == X:
            answer += 1
            check[i], check[j] = 1, 1 #쌍이 확정되면 1로 체크
            
print(answer)

2. 완전탐색 접근(투 포인터)

이전 접근 방식에서는 $O(N^2)$의 시간 복잡도로 인해, 극단적인 입력값에서 시간 초과가 발생했을 것이다. 이를 해결하기 위해 정렬과 투 포인터를 활용할 것이다.

• 정렬 : 배열을 오름(내림)차순으로 정렬한다.
• 투 포인터 : 불가능한 경우의 수를 제거해가며 탐색하는 방식이다. 단순한 반복문을 이용한 완전 탐색의 업그레이드 버전이라고 생각하면 된다.

입력값이 다음과 같이 주어졌다고 하자.

\[\text{sorted(arr)} = [1, 2, 3, 4, 6], \quad X = 6\]

이제 정렬된 리스트를 가지고 투 포인터를 적용해보도록 하겠다.
처음에는 포인터를 리스트의 양 끝에 배치한다. (문제에 따라 포인터의 위치를 다르게 설정해도 된다.)

1. start = 1, end = 6를 가리킬 때

   • 두 수의 합: $1 + 6 = 7$
   • $X$ 보다 크므로, $X$에 가까워지기 위해 end 포인터를 왼쪽으로 이동한다.

2. start = 1, end = 4를 가리킬 때

   • 두 수의 합: $1 + 4 = 5$
   • $X$보다 작으므로, $X$에 가까워지기 위해 start 포인터를 오른쪽으로 이동한다.

이렇게 불가능한 경우를 제거하면서 탐색할 수 있어, 이전 접근 방법보다는 훨씬 효율적이다. 정렬과 투 포인터를 합쳐도 시간복잡도 $O(N \log N)$을 가진다..!

코드 구현

N = int(input())
arr = sorted(list(map(int, input().split()))) #정렬된 상태
X = int(input())

s_p = 0
e_p = N-1
answer = 0

while s_p < e_p:
    
    if arr[s_p] + arr[e_p] == X:
        answer += 1
        s_p += 1
        e_p -= 1   
    elif arr[s_p] + arr[e_p] > X: 
        e_p -= 1    
    else:
        s_p += 1

print(answer)

회고

매번 접근하여 가능성을 확인하는 방식에서, 가능성을 확인하면서 탐색 범위를 줄여가는 방식으로 최적화할 수 있다는 점을 배웠다.