[백준 2336] 굉장한 학생 (Platinum II)

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

 

 일단 등수대로 적혀 있던 것을 나름대로 잘 해석해서 함수 개개인에게 점수를 부여한다. 점수는 Student 구조체 하나를 만들어서, 거기다 저장할 수 있다.

 

 이제 문제를 단순화해서 만약 시험 결과가 2개만 주어진다면 문제를 어떻게 풀지 생각해보자. 나라면 아마 다음과 같은 그림을 그려서 풀 것이다.

 그림의 화살표가 나타내는 것은 알고리즘의 흐름이다. 우선 x좌표가 가장 큰 점에서부터 출발해, x좌표가 점점 작아지는 순으로 각 점들을 방문해 나간다. 이렇게 하기 위해서는 당연하지만 정렬이 필요하다. 이렇게 하면 x좌표에 대한 비교가 이미 끝났으므로 y좌표에 대한 비교만 하면 된다는 사실을 알 수 있다. 점 하나를 방문할 때마다 그 점이 이전까지 방문했던 점들 중 가장 y좌표가 크다면 그 점을 굉장한 학생으로 체크하면 된다. 이 과정은 점 하나당 O(1)에 해결 가능하다(자세한 설명은 생략).

 

 이제 그림을 잘 관찰하면 굉장한 학생으로 기록된 학생만을 남겼을 때 화살표 방향이 모두 왼쪽 위를 향한다는 사실을 알 수 있다. 이는 쉽게 증명할 수 있는데 생략하고, 어쨌든 이런 그림을 LU-그림이라고 정의하자. (용어는 내가 임의로 붙인 것이다.)

 

 이제 시험 3개가 있을 때도 비슷하게 풀 수 있을 것이다. 우선 z좌표가 큰 순으로 점을 정렬한다. z좌표에 대해서는 이미 정렬을 해서 비교가 끝났으므로 x좌표, y좌표만 신경을 쓰면 된다. z좌표를 없애고 x, y좌표만 표시했을 때 다음과 같은 그림이 된다고 가정하자.

 

 

 그러면 이제 다음과 같이 각 점들을 관리하면 된다. 핵심은 점들을 항상 LU-그림이 되도록 관리하는 것이다.

1. 1번째 점을 굉장한 학생으로 기록하고 좌표평면에 표시한다. (좌표평면에 1 있음)
2. 2번째 점은 현재 LU-그림의 왼쪽 아래에 있으므로 무시하고 넘어간다.
3. 3번째 점은 LU-그림의 위에 있으므로 굉장한 학생으로 기록하고 좌표평면에 표시한다. (좌표평면에 3, 1 있음)
4. 4번째 점은 LU-그림의 오른쪽에 있으므로 굉장한 학생으로 기록한다. 1번째 점은 4번째 점의 왼쪽 아래에 있으므로 1번 점을 지운다. 4번째 점을 좌표평면에 표시한다. (좌표평면에 3, 4 있음)
5. 5번째 점은 LU-그림의 오른쪽에 있으므로 굉장한 학생으로 기록한다. 5번째 점을 좌표평면에 표시한다. (좌표평면에 3, 4, 5 있음)
6. 6번째 점은 LU-그림의 왼쪽 아래에 있으므로 무시하고 넘어간다.
7. 7번째 점은 LU-그림의 위에 있으므로 굉장한 학생으로 기록한다. 3번째 점은 7번째 점의 왼쪽 아래에 있으므로 3번 점을 지운다. 7번째 점을 좌표평면에 표시한다. (좌표평면에 7, 4, 5 있음)

 

 이제 이 절차를 잘 처리할 자료구조를 선택한다. 내부 데이터가 정렬되어 있는 자료구조와 임의 위치 탐색, 삽입, 삭제가 빠른 자료구조가 필요하므로 BBST, 그 중에서도 map을 선택하여 문제를 해결한다. map에는 현재 보고 있는 LU-그림의 각 점들의 x좌표를 key, y좌표를 value로 보고 저장을 한다. 그러면 당연한 얘기지만 map이 갖고 있는 점들은 key가 늘어날수록 value가 줄어드는 모양을 갖게 된다. 일종의 monotone bbst map이라고 생각할 수 있는 것이다.

 

#include <bits/stdc++.h>

struct Student {
    int s1, s2, s3;
    constexpr static int mem_num = 3;
};

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<Student> data(n);
    for (int j = 0; j < n; ++j) {
        int x;
        std::cin >> x;
        data[x - 1].s1 = n - j;
    }
    for (int j = 0; j < n; ++j) {
        int x;
        std::cin >> x;
        data[x - 1].s2 = n - j;
    }
    for (int j = 0; j < n; ++j) {
        int x;
        std::cin >> x;
        data[x - 1].s3 = n - j;
    }
    
    int ret = 0;
    
    std::sort(data.begin(), data.end(),
              [](const Student& l, const Student &r) {
        return l.s1 > r.s1;
    });
    
    std::map<int, int> map;
    for (const Student& student : data) {
        auto lbd = map.lower_bound(student.s2);
        if (lbd != map.end() && student.s3 < lbd->second) {
            continue;
        }
        
        ret += 1;
        auto it = map.insert({student.s2, student.s3}).first;
        if (it == map.begin()) {
            continue;
        }
        it = std::prev(it);
        
        while (it->second < student.s3) {
            it = map.erase(it);
            if (it == map.begin()) {
                break;
            }
            it = std::prev(it);
        }
    }
    
    std::cout << ret << '\n';
}

#ifndef LOCAL
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}
#endif