[Algospot] 알고스팟 NERD2 너드인가, 너드가 아닌가? 2

출처: https://algospot.com/judge/problem/read/NERD2

 Input 

2

4

72 50

57 67

74 55

64 60

5

1 5

2 4

3 3

4 2

5 1

 

 Output 

8

15

 

x, y좌표를 좌표명면상의 점으로 표현 → (x, y)를 직사각형의 우측 상단 좌표로 생각.

새로운 신청자(좌표)가 추가될 때마다 기존 영역에 지배 여부(isDominated)로 너드 여부 확인

※ 한 점 a가 다른 점 b보다 오른쪽 위에 있을 때, a가 b를 ‘지배한다’고 표현

- 기존의 좌표(a, b) 중에서 새로운 좌표(x, y)와 비교해서 x < a && y < b를 판단

   즉, 사각형 영역에서 새로운 좌표보다 우측 상단에 위치한 꼭지점이 있는지 확인하는 것입니다.

① 새로운 좌표가 너드인 경우:

    기존 좌표들 중에서 더이상 너드가 아닌 좌표를 찾아 제거

② 새로운 좌표가 너드가 아닌 경우:

    기존 좌표 변동 X

 

지배당하지 않는 점들을 모두 비교하는 쉬운 방법은 배열에 좌표를 저장하여 비교하는 것입니다.

하지만 N은 최대 50,000이기 때문에 TLE 발생

지배 여부를 판단하기 위해 기존의 모든 좌표를 비교하기 보다 최적화가 필요.

 

①~④ 좌표가 존재하는 상태에서 새로운 P(a, b)가 들어왔다고 가정.

P 좌표의 지배여부를 확인하기 위해서는 P좌표보다 우측에 있으면서 위쪽에 있는 좌표를 찾으면됩니다.

ⅰ) a < x 조건에 해당하는 좌표를 후보군으로 들고 옵니다. → ③, ④

ⅱ) 후보군 중에서 b < y 조건을 만족하는 것이 있는지 확인

      존재하지 않는 경우 P 좌표는 지배되지 않습니다.

ⅲ) P 좌표는 너드이므로 기존 좌표들 중 더이상 너드가 되지 않는 좌표를 찾아 제거합니다.

ⅳ) 점 P 기준 x < a 후보군을 찾습니다. ①, ②

ⅴ) 후보군 중 y < b에 해당하는 좌표를 제거

* 이때 좌표들이 형성되어 있는 모양을 분석하면 계단 형태로 되어 있는것을 확인할 수 있습니다.

    이는 지배당하지 않는 점들을 x 좌표 기준으로 오름차순 정렬하면 y좌표가 자동으로 내림차순 정렬됩니다.

    따라서 A(a, b) 지배 여부를 판단할 때, 바로 오른쪽에 위치한 점의 y값을 비교하면 됩니다.

    또한, A(a, b)가 지배되지 않은 면서 기존 점들 제거여부를 탐색할 때도,

             x 좌표가 가까운 점들을 탐색할 때, y > b에 해당하는 점을 찾으면 탐색 종료.

             즉, A에 지배당하지 않는 점이 등장하면 곧장 종료

①~④ 좌표가 존재하는 상태에서 새로운 Q(c, d)가 들어왔다고 가정.

ⅰ) 점 Q보다 우측에 있는 점들 중 x 좌표 기준 가장 가까운 점만 비교

      즉, 바로 우측에 있는 ②과 y좌표 비교.

ⅱ) y > d 이므로 Q는 지배되므로 기존 점들이 너드 유지

     (※ 만약 지배되지 않아 기존 점들의 너드 여부를 확인할 경우,

     좌측 영역에서 x 좌표 기준 가장 가까운 ①에서 y  > d 이므로 바로 탐색이 종료됩니다.)

* STL의 균형 잡힌 이진 검색 트리로 구현되어 있는 map<int, int> 이용해서 점들을 저장.

* map<int, int>::lower_bound(x)로 트리에 포함된 x 이상의 키 중 가장 작은 값을 돌려받습니다.

---

#include <iostream>
#include <map>
using namespace std;

int C, N;
map<int, int> coords; // coords[x] = y

bool isDominated(int x, int y) {
    // 해당 점(x, y)에서 바로 오른쪽에 있는 좌표
    // (오른쪽에 있는 점들 중 가장 왼쪽에 있는 점)
    map<int,int>::iterator it = coords.lower_bound(x); 
    // 해당 점(x, y)보다 오른쪽에 있는 점이 없다면 지배받지 않습니다.
    if (it == coords.end())
        return false; 
    // 해당 점(x, y)에서 바로 오른쪽에 있는 좌표가 존재하면서
    // y 위치까지 작으면 지배받습니다.
    if (y < it->second) return true;
    else return false;
}

void removeDominated(int x, int y) {
    // 해당 점(x, y)에서 바로 오른쪽에 있는 좌표
    map<int, int>::iterator it = coords.lower_bound(x);
    // (x, y)보다 왼쪽에 있는 점이 없는 경우
    if (it == coords.begin()) return;

    // 왼쪽에 점들이 존재하는 경우, y값을 비교하여 제거처리 
    --it;
    while (true) { //it은 항상 바로 왼쪽 좌표
        // 점(x, y)의 y값보다 크므로 탐색 종료
        if (it->second > y) break; 
        // 더 이상 비교할 왼쪽점이 없는 경우
        if (it == coords.begin()) {
            coords.erase(it);
            break;
        }
        else {
            // 점(x, y)의 y값보다 작으므로 제거
            // (iterator는 계속 탐색할 수 있게 설정)
            map<int, int>::iterator jt = it; //왼쪽 좌표를 제거하고 하나 땡겨준다.
            --jt; 
            coords.erase(it);
            it = jt;
        }
    }
}

// 새로운 점(x, y)를 추가하여 지배 여부에 따른 처리
int registered(int x, int y) {
    // (x, y)가 지배당하면 추가 없이 그대로 반환
    if (isDominated(x, y)) return coords.size(); 
    // 지배당하지 않은 경우, 기존의 점 중에 지배당하는 것을 제거
    removeDominated(x, y);
    coords[x] = y;
    // 변경된 수치로 반환
    return coords.size();
}

int main()
{
    cin >> C;
    while (C--) {
        cin >> N;
        coords.clear();
        int result = 0;
        for (int i = 0; i < N; i++) {
            int x, y;
            cin >> x >> y;
            // 점들을 추가하면서 너드 결과 확인
            result += registered(x, y);
        }
        cout << result << endl;
    }
}