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

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

 

 

정수인 요소 값들이 주어졌을때 2개의 요소를 선택하여 합이 K와 가까운 조합의 개수를 출력하는 문제이다.

 

요소의 개수가 100만이기 때문에 O(N^2)으로는 풀 수 없다 따라서 O(N)으로 풀 수 있는 방법을 찾아야 한다.

 

그렇기에 요소들의 크기가 서로 다르기 때문에 정렬하여 투 포인터 알고리즘을 사용하여 조합을 찾아보았다.

 

 

투포인터 알고리즘을 사용할때 left, right 포인터를 지정해야되는데 이때 음수의 값이 있기에 오른쪽 포인터는 맨 우측으로 잡으며 안쪽으로 좁혀 나갔다.

 

음수가 있고 K값에 근접해야하기 때문에 K값과 차이를 절댓값을 사용하여 갱신해 주었다. 

K값과 두 포인터들의 합의 차이의 절댓값이 0이랑 근접해야 가깝기 때문이다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int T, N, K;
vector<int> v;

void solve() {
    int minval = MAX;
    sort(v.begin(), v.end());

    int left = 0;
    int right = N-1;
    int cnt = 0;

    while(left < right) {
        int val = v[left] + v[right];

        if(val == K) left++, right--;
        else if(val > K) right--;
        else if(val < K) left++;

        int vals = abs(K - val);

        if(vals == minval) cnt++;

        if(minval > vals) {
            cnt = 1;
            minval = vals;
        }
    }

    cout << cnt << endl;
}

void input() {
    cin >> T;

    while(T--) {
        cin >> N >> K;

        for(int i = 0; i < N; i++) {
            int a;
            cin >> a;
            v.push_back(a);
        }

        solve();

        v.clear();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}