[백준 3273번] 두 수의 합 (C++, Python)
https://www.acmicpc.net/problem/3273
3273번: 두 수의 합
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는
www.acmicpc.net
이번 포스트에서는 백준 알고리즘 문제인 두 수의 합을 포스트 하도록 하겠습니다.
해당 문제는 solved.ac 기준 실버 3에 위치한 문제입니다.
먼저 문제입니다.
N과 길이 N의 수열, X를 입력받고, 수열에서 두 수의 합이 X가 되는 개수를 출력하는 문제입니다.
일반적으로는 이중 for문을 사용하여 쌍을 구하면 해결할 수 있지만, 시간제한이 1초이고, N이 최악의 경우 10만까지 주어지기 때문에 O(N^2)인 이중 for문을 통해서는 해결할 수 없습니다.
따라서, 해당 문제는 퀵정렬과 투포인터를 활용하여 O(N log N)에 해결할 수 있습니다.
먼저 투 포인터는 이름 그대로, 포인터를 2개를 가지고 값을 도출하는 기법 입니다.
해당 문제에서는 값 2개의 합이 X가 되는 횟수를 구해야하므로, 이를 위해 배열을 퀵정렬을 통해 오름차순으로 만들어줍니다.
이때, 가장 첫 값과, 가장 마지막 값은 각각 제일 작은 값과 제일 큰 값입니다. 이 둘의 합이 X보다 작다면, 두번째로 작은 값을 선택합니다. (왼쪽 포인터 이동)
이 둘의 합이 X보다 크다면, 두번째로 큰 값을 선택합니다. (오른쪽 포인터 이동)
위의 예시로 볼때, X보다 작다면 그 다음으로 큰 값을 선택하고, X보다 크다면 그 다음으로 작은 값을 선택하는 구조를 띄게됩니다. 그러므로 퀵정렬을 통해 오름차순 정렬을 한 후, 투포인터 기법으로 해결합니다.
다음은 C++ 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>
using namespace std;
int compare(const void* a, const void* b) {
return *(int*)a > *(int*)b ? 1 : (*(int*)a < *(int*)b ? -1 : 0);
}
int main() {
int n, x, res = 0;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++)
cin >> arr[i];
cin >> x;
qsort(arr, n, sizeof(int), compare);
int lp = 0, rp = n - 1;
while(lp < rp) {
if(arr[lp] + arr[rp] < x)
lp++;
else if(arr[lp] + arr[rp] > x)
rp--;
else {
lp++;
rp--;
res++;
}
}
cout << res;
return 0;
}
|
cs |
위에서 compare 함수는 퀵정렬에서 오름차순을 위한 비교함수입니다.
다음은 Python 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split(" ")))
x = int(sys.stdin.readline())
res = 0
arr.sort()
lp = 0
rp = n - 1
while lp < rp :
if arr[lp] + arr[rp] < x :
lp += 1
elif arr[lp] + arr[rp] > x :
rp -= 1
else :
lp += 1
rp -= 1
res += 1
print(res)
|
cs |
해당 문제는 이중 for문을 통해 값을 도출하는게 안되기 때문에 O(N^2)보다 적은 알고리즘 중에서 퀵 정렬과 투포인터를 활용해 배열을 1번만 접근하는 방법을 도출하는 것이 중요한 문제였던것 같습니다.
필자는 파이썬 코드를 작성할 때, 퀵정렬을 직접 구현하였으나 sort() 함수와 어떤 다른점이 있는지 런타임 에러가 생겨 파이썬에 내재된 퀵정렬 기반 sort함수로 해결했습니다. (오류 상 퀵 정렬을 재귀로 들어가는 과정에서 최대 재귀 횟수를 초과한 걸로 추정)
다음 포스트에서는 또 다른 백준 알고리즘 문제로 포스트하도록 하겠습니다. 감사합니다.