[Algorithm]Baekjoon 9024번 :: 두 수의 합

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
int t, n, k;
int arr[1000001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    while (t--)
    {
        cin >> n >> k;
        
        for (int i = 0; i < n; ++i)
        {
            cin >> arr[i];
        }
 
        sort(arr, arr + n);
 
        int left = 0;
        int right = n - 1;
        int minGap = 0x3f3f3f3f;
        int minGapCount = 0;
 
        while (left < right)
        {
            int num = arr[left] + arr[right];
 
            int gap = abs(k - num);
            
            if (gap == minGap) // 현재까지의 최소갭과 동일하면 카운팅
            {
                ++minGapCount;
            }
            else if (gap < minGap) // 더 작으면 업데이트.
            {
                minGap = gap;
                minGapCount = 1;
            }
 
            if (num <= k)
            {
                ++left;
            }
            else
            {
                --right;
            }
        }
 
        printf("%d\n", minGapCount);
    }
}
 
 

 

약간 투포인터문제의 정석 느낌이 나는 문제다.

타겟값k와 가장 가까운 두 수의 합을 구한다음 그 합의 개수까지 구해야 한다.

배열을 정렬 후, 양끝에 두개의 포인터를 둔다음 탐색을 시작할 건데, 값이 오름차순으로 정렬되어 있기 때문에 두 포인터가 가리키는 숫자의 합이 작을경우 값을 늘려야하니까 왼쪽포인터를 한칸 오른쪽으로 옮긴다. 

두 숫자의 합이 크면 값을 줄여야하니까 오른쪽포인터를 한칸 왼쪽으로 옮긴다.

 

매번 옮길때마다 k와의 gap을 업데이트 해주면 되는데 최종출력은 개수를 출력하는 거라서 매 탐색 시 현재까지의 최소gap값과 일치하면 카운팅 해주면 된다. gap값이 더 작은값을 발견하면 다시 초기화해주면 되고.