백준 9024번: 두 수의 합 [C++]

작성일 | In
골드 V 골드 V

문제

두 수의 합
주어진 수열에서 두 원소를 골라 k와 합이 가장 가까운 모든 경우를 찾는 문제입니다.

풀이

$n$의 크기가 최대 $10^6$이므로 모든 경우를 탐색하면 $O(n^2)$으로 시간초과를 받게 됩니다. 따라서 모든 경우를 탐색하는 것이 아니라 조건을 만족하게끔 그리디하게 탐색해야 합니다.

방법에는 두가지가 있는데, 하나는 정렬+이분탐색이고, 하나는 정렬+두 포인터입니다. 이분탐색을 이용하면 $O(2nlogn)$이고, 두 포인터를 이용하면 $O(nlogn + n)$으로 조금 더 빠릅니다. 이 글에서는 두 포인터로 풀이해 보겠습니다.

먼저 주어진 수열을 정렬합니다. ($O(nlogn)$)
그리고 포인터 두개를 수열의 처음, 끝에 각각 지정합니다. 만약 두 포인터가 가리키는 두 수의 합이 k보다 작다면 왼쪽 포인터를 오른쪽으로 옮겨 합이 커지게끔 합니다. k보다 크다면 반대로 오른쪽 포인터를 왼쪽을 옮기면 됩니다. ($O(n)$)

다만 가장 가까운 모든 경우의 수를 찾아야 하므로, k와 두 수의 합의 차를 저장해 둡니다. 포인터를 옮겨가며 탐색하다가 차가 같다면, 경우의 수를 하나 늘려주면 되고, 차가 작다면 경우의 수를 1로 초기화 해주면 됩니다.

코드

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;

        vector<ll> arr(n);

        for (int i = 0 ; i < n ; i++) {
            cin >> arr[i];
        }

        sort(arr.begin(), arr.end());

        ll minDist = LLONG_MAX;
        int count = 0;


        int left = 0, right = n - 1;
        while (left < right) {
            if (abs(arr[left] + arr[right] - k) == minDist) {
                count++;
            } else if (abs(arr[left] + arr[right] - k) < minDist) {
                minDist = abs(arr[left] + arr[right] - k);
                count = 1;
            }

            if (arr[left] + arr[right] <= k) {
                left++;
            } else {
                right--;
            }
        }

        cout << count << '\n';
    }


    return 0;
}

백준 9024번: 두 수의 합 [C++]