[코드트리 챌린지] 8주차 - +1-1 technique / 가장 많이 겹치는 구간

마의 투포인터 돌파

 

https://www.codetree.ai/missions/8/problems/section-with-maximum-overlap/description

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

 

코드:

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

int n;
int x1[100005]; // 시작점
int x2[100005]; // 끝점
vector<pair<int, int>> arr;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x1[i] >> x2[i];
    }

    // 시작점엔 +1 끝점엔 -1로 설정하여 배열에 넣음
    for (int i = 0; i < n; i++) {
        arr.push_back(make_pair(x1[i], 1));
        arr.push_back(make_pair(x2[i], -1));
    }

    // x 좌표를 기준으로 정렬
    sort(arr.begin(), arr.end());

    // 어떤 점 k를 기준으로 앞에 존재하는 x 좌표의
    // 값들을 모두 더했을 때 나온 값이 겹치는 선분의 개수를 의미함
    // k 기준 앞에 존재하는 선분은 합이 0이 되기 때문

    int sum = 0; // 모든 좌표를 돌면서 그 좌표의 값을 더함
    int maxSum = 0; // sum 중 최대값

    // 모든 좌표를 돌면서 그 좌표값을 더한다는 것은
    // 모든 위치를 어떤 점 k로 잡아 그 앞에 존재하는 좌표의
    // 값을 모두 더했을 때를 계속해서 sum에 갱신한다는 것을 의미함
    // 그 중 최대값을 가장 많이 겹치는 부분임
    for (int i = 0; i < 2 * n; i++) {
        int x, v; // v는 +1 or -1
        tie(x, v) = arr[i];

        sum += v;
        maxSum = max(maxSum, sum);
    }

    cout << maxSum;
}

선분의 시작과 끝점을 입력을 받습니다.

그 중 시작점의 값을 +1 , 끝점의 값을 -1로 설정하여 vector에 넣습니다.
이후 x 좌표를 기준으로 정렬시키도록 합니다.

이때 우리가 구해야 할 값은 선분이 가장 많이 겹치는 구간입니다.
이를 구하기 위해서는 모든 점을 기준으로 삼아 겹치는 선분의 개수가 얼마인지 파악하는 것 입니다.

따라서 for문을 통해 모든 점을 돌면서 그동안의 x좌표 값들의 합을 sum에 구합니다.
즉, sum은 i = n 이라고 할 때 x 좌표가 n인 위치에 겹치는 선분의 수를 의미합니다.

maxSum은 모든 점을 순회하면서 그 중 가장 많이 겹치는 부분을 구해야하므로 sum과 비교하여
계속 값을 갱신합니다.