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

문제링크 : https://www.acmicpc.net/problem/9024

9024번: 두 수의 합

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, N, K, arr[1000001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T;
    while(T--)
    {
        cin >> N >> K;
        for(int i=0; i<N; i++) cin >> arr[i];
        sort(arr, arr+N);

        int l=0, r=N-1, minV = MAX, cnt = 0;
        while(l<r) //두 포인터
        {   
            int num = arr[l] + arr[r];
            if(num == K) l++, r--;
            else if (num > K) r--;
            else if (num < K) l++;

            if(minV == abs(K-num)) cnt++; //같은 최솟값 카운팅
            if(abs(K-num) < minV) //K에 제일 가까운 작은 값 저장
            {
                minV = abs(K-num); //최솟값 저장
                cnt = 1; //해당 최솟값부터 다시 카운팅
            }
            
        }

        cout << cnt << "\n";
    }

    return 0;
}

 

두 포인터 알고리즘을 사용한 문제이다.

해당 알고리즘을 사용하기 위해 정렬을 시행해준다.

좌우측 양 끝에 포인터를 하나씩 두고 해당 포인터를 합한 값에 따라 포인터를 이동하게 된다.

 

값이 K와 같을 경우, 원하는 값을 찾았고 이후에도 있는지 체크하기 위해 양쪽 포인터 모두 이동시킨다.

값이 K보다 클 경우, 값을 감소시키기 위해 우측 포인터를 이동시킨다.

값이 K보다 작을 경우, 값을 증가시키기 위해 좌측 포인터를 이동시킨다.

 

여기서 추가로 주의해야 할 점은 두 포인터의 합이 단순히 K를 가리키는 것을 찾는 것이 아니라, K와 가장 가까워지는 순간과 해당 값의 횟수를 찾는 것이다.

따라서 abs(K-num)을 통해 K와 차이가 가장 작은 값을 구하고 (같을시 0), 해당 최솟값을 저장한 minV의 값이 새로운 포인터로 구했을 때 또 똑같은 최솟값이 발견되면 해당 값에 대해 카운팅을 해준다.

새로운 최솟값이 발견되면 카운팅은 다시 1부터 시작하게 된다.