[코드트리] +1-1 Technique | C++

출처

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

들어가면서

코드트리 문제를 풀다보면 수직선 상 특정 한 점에서 겹치는 서로 다른 선분의 개수를 구하는 문제를 만나게 된다.
 
단순하게 for문으로 해결한다면 시간초과가 발생하므로 코드트리에서 설명하는 '+1-1 Technique' 알고리즘을 사용해야만 한다.

+1-1 Technique 알고리즘이란?

모든 선분에 대한 시작점과 끝점에 가중치 +1과 -1을 각각 부여함으로써 x의 값이 증가하는 순서대로 정렬하는 방법을 의미한다.
 
각각의 가중치는 1차원 배열에 저장함으로써 특정 한 점에서 겹치는 선분의 개수를 구할 수 있게 된다.

---

가장 많이 겹치는 구간 | C++

#include <iostream>
#include <tuple>

using namespace std;

int main(void) {
    int n;
    cin >> n;
    int checked[200001] {};
    for(int i{ 0 }; i < n; i++) {
        int x1, x2;
        cin >> x1 >> x2;
        checked[x1]++;
        checked[x2]--;
    }
    int sum_val = 0;
    int max = checked[1];
    for(int& ele : checked) {
        sum_val += ele;
        max = (max < sum_val) ? sum_val : max;
    }
    cout << max;
    return 0;
}

코드 리뷰

문제에서 x 좌표의 최댓값이 200,000이므로 편의상 200,001로 인덱스와 x좌표의 값을 동일하게 설정하여 x좌표의 가중치를 저장할 checked 배열을 선언하였다.
 
n개의 선분의 시작점과 끝점을 변수 x1과 x2에 저장하고 각각의 가중치 +1과 -1을 checked 배열에 저장한다.
 
문제에서는 가장 많이 겹치는 구간의 횟수를 구하는게 목표이므로 checked 배열을 순회하면서 각 점의 겹치는 구간의 개수를 확인하고 그 구간의 개수가 최댓값이면 변수 max를 업데이트한다.

서로 다른 구간의 수 | C++

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
    int n;
    cin >> n;
    vector<tuple<long long, int, int>> v;
    for(int i{ 0 }; i < n; i++) {
        long long x1, x2;
        cin >> x1 >> x2;
        v.push_back(make_tuple(x1, +1, i));
        v.push_back(make_tuple(x2, -1, i));
    }
    int result = 0;
    unordered_set<int> s;

    sort(v.begin(), v.end()); //오름차순
    for(auto p : v) {
        int w = get<1>(p);
        if(w == 1) {
            if(s.size() == 0) {
                result++;
            }
            s.insert({get<2>(p)});
        } else { // w == -1
            s.erase(get<2>(p));
        }
    }
    cout << result;
    return 0;
}