[코드트리 챌린지] 6주차 Two Pointer - Two Pointer / 정수 두 개의 합 2

 

https://www.codetree.ai/missions/8/problems/sum-of-two-integers-2/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

int n, k;
int arr[100005];

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

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

    // 경우의 수를 더 쉽게 구하기 위해 sort
    sort(arr, arr + n);

    int j = n-1; // 맨 끝점을 포인터로 잡음
    int ans = 0; // 경우의 수를 저장할 변수

    for (int i = 0; i < n; i++) {
        
        // j가 0보다 크고 i와j가 가리키는 지점의 합이
        // k 보다 큰 경우 j를 감소시킴
        while (j > 0 && arr[i] + arr[j] > k)
            j--;

        // i가 j를 넘는 경우, 두 수의 합이 k 이하인 수가 존재하지
        // 않는 경우임
        if (i >= j) break;


        // ans에 j - i를 더함. sort를 진행한 이유가 이것인데
        // sort를 통해 정렬해줬으므로 while을 빠져나온 경우 arr[i] + arr[j]의 합은
        // 최대가 되며 k 이하의 값을 가짐. (j > 0에 의해 빠져나온 경우 위 if문에서 걸러짐)
        // 따라서 arr[i]와 i~j사이 가리킬 수 있는 모든 값의 각 합은 k보다 작을 수 밖에 없음
        // 그렇기에 j - i는 그 사이의 존재하는 모든 경우의 수를 더해준 것이라고 할 수 있음
        // 이후 i가 증가한 경우에도 arr[i] + arr[j]의 값은 k 이하임이 분명함
        // arr[i-1] < arr[i] 이므로 증가한 만큼 합의 값이 줄어들기 때문
        ans += j - i;
    }

    cout << ans;

}

 

위 투포인터 문제의 경우 다른 문제와 다르게 한 포인터가 끝에서 시작하는 특이점을 가지고 있습니다.

평소대로 문제를 해결하려 하여 어려움을 겪은 문제중 하나라 해석을 보고 이해한 뒤 풀이를 작성하였습니다 ㅠㅠ..