[종만북] NERD2

 

ac 코드입니다

#include <iostream>
#include <map>
using namespace std;
 
//현재 다른 점에 지배당하지 않는 점들의 목록을 저장
//coords[x] = y
map<int, int> coords;
//새로운 점(x,y)가 기존의 다른 점들에 지배당하는지 확인한다.
bool isDomianted(int x, int y) {
    //x보다 오른쪽에 있는 점 중 가장 왼쪽에 있는 점을 찾는다.
    map<int, int>::iterator it = coords.lower_bound(x);
    //없다면 지배당하지 않는다.
    if (it == coords.end()) return false;
    //이 점은 x보다 오른쪽에 있는 점 중 가장 위에 있는 점이므로,
    //(x,y)가 어느 점에 지배되려면 이 점에도 지배되어야 한다.
    return y < it->second;
}
//새로운 점(x,y)에 지배당하는 점들을 트리에서 지운다.
void removeDominated(int x, int y) {
    map<int, int>::iterator it = coords.lower_bound(x);
    //(x,y)보다 왼쪽에 있는 점이 없다!
    if (it == coords.begin()) return;
    --it;
    while (true) {
        //it가 표시하는 점이 (x,y)에 지배되지 않는다면 곧장 종료
        if (it->second > y) break;
        //이전 점이 더이상 없으면 종료
        if (it == coords.begin()) {
            coords.erase(it);
            break;
        }
        //이전 점으로 이터레이터를 하나 옮겨 놓고 it를 지운다
        else {
            map<int, int>::iterator jt = it;
            --jt;
            coords.erase(it);
            it = jt;
        }
    }
}
//새 점(x,y)가 추가되었을 때 coords를 갱신하고
//다른 점에 지배당하지 않는 점들의 개수를 반환한다.
int registed(int x, int y) {
    if (isDomianted(x, y)) return coords.size();
    removeDominated(x, y);
    coords[x] = y;
    return coords.size();
}
int main()
{
    int c; scanf("%d", &c);
    while (c--) {
        int n; scanf("%d", &n);
        int ans = 0; //참가 자격이 안되는 사람의 수
        while (n--) {
            int p, q; //문제, 그릇
            scanf("%d %d", &p, &q);
            ans += registed(p, q);
            
        }
        printf("%d\n", ans);
        coords = {};
    }
    return 0;
}
 

 

풀이

책에 있는 코드를 주석도 빼놓지 않고 베끼긴했지만.. ㅋㅋ

c++ stl <map>을 사용하는데에 있어서 배울점이 많은 코드였다.

 

우선 이 문제를 푸는데에 가장 중요하다고 느꼈던 점은

"너드인 좌표들을 x좌표(문제의 수)가 증가하는 순서대로 정렬해 보면 y좌표(그릇의 수)는 항상 감소하게 되어있다"

는 너드의 특성을 잘 파악해야한다.

 

이 말을 그림으로 이해하면, 좌표들을 찍어 원점에서 부터의 직사각형으로 각각 연결 할 때

그림은 왼쪽 위에서부터 오른쪽 아래로 향하는 계단 형식이 나타나게 된다.

그렇게 되면 새로운 점(p,q)가 추가될 때 이 점이 지배당하는지 아닌지를 확인하려면,

이미 있는 좌표들 가운데에서 바로 오른쪽에 있는 점을 찾고, 높이가 그 점보다 높은지, 낮은지를 파악해야한다.

만약 낮다면 그 점은 추가될 필요가 없기 때문에 무시해도 좋다.

 

그렇다면 다음엔 점이 추가된 이후의 상황을 고려해봐야하는데,

점이 추가되고, 기존에 있던 너드의 점들이 추가된 점에 의해 지배당할 수 있기 때문이다.

이를 확인하기 위해선 간단하게 추가된 점 기준 왼쪽에 있는 점들의 높이를 순차적으로 비교하면 된다.

 

만약 왼쪽 점의 높이가 기존 점보다 높다면, 더 왼쪽에 있는 점들은 반드시 더 높기 때문에(계단 형)

그대로 지나가면 되고

만약 낮다면, 그 점은 추가된 점에게 지배당하기 때문에 지워주어야 한다.

 

이러한 방식을 이용하면, 점이 추가될 때마다 너드의 수를 구할 수 있다.

 

이 내용들을 구현으로 옮겨보자.

 

구현

그러면 이제 구현을 해야하는데,

풀이 맨 첫 부분에서 (x,y) 좌표를 정렬한다고 하였다.

 

만약 문제에서 주어질 때 마다 (x,y)좌표들을 vector에 넣고 sort로 정렬한다면,

o(nlogn)이 걸리고, 나머지 연산을 하는데 또 시간이 소요되기 때문에 문제에서 주어지는 n제한(5만)에

시간초과가 날 가능성이 매우 높다.

 

따라서 하나의 원소가 추가될 때 o(logn)이 걸리는 이진 탐색 트리 STL <map>을 사용하면 이 문제를 풀기 아주 편리한데, map은 원소를 넣을 때 알아서 정렬을 해주기 때문이다. (삽입에 걸리는 시간복잡도 : o(logn))

 

그럼 우린 map을 사용해 구현을 할 것이고

좌표(원소 쌍)을 삽입하기 전에 해야할 일들이 두 가지 있다.

• 삽입될 원소가 기존 점들에 의해 지배 받는가?
• 삽입될 원소가 기존 점을 지배하는가?

이 부분을 체크해야하는데

우선 첫 번째, 삽입될 원소가 기존 점들에 의해 지배받는지에 대한 여부는

 

아까 그림에서 살펴보았듯, 바로 오른쪽 원소(즉, map에 저장된 원소 중 lower_bound(new_x))를 보고

만약 없으면 false를 리턴, 있다면 높이 값을 비교해 삽입 될 원소가 더 높으면 true를 리턴한다.

 

만약 리턴값으로 false를 반환했다면 새로운 점은 그냥 무시해도 되기 때문에 기존 map의 size를 반환하는 것으로 끝난다. 이 부분에 대한 함수는 위의 isDomiated 입니다!

 

 

두 번째, 이제 삽입될 원소가 기존 점을 지배하는가? 에 대해서 살펴볼 차례이다.

 

우선 기존 점들 중 삽입될 원소보다 오른쪽에 있는 값들은

푼 문제의 수가 많기 때문에 절대 삽입될 원소에 지배받지 않는다.

 

따라서 우리가 봐야할 점은 삽입 원소 기준 왼쪽에 있는 값들이다.

이 값들 또한 map의 lower_bound(new_x)를 통해 찾을 수 있는데 만약 반환값이 map.begin()이라면 

왼쪽에 있는 값들이 없기 때문에 바로 return해주고, 아니라면 한 칸씩 왼쪽으로 이동하면서

높이가 더 낮은 점들이 있는지 확인한다.

 

만약 그 점이 없다면 이후에도 없기 때문에(계단식이므로)

break를 하고

 

만약 그 점이 있다면 erase를 사용하여 지운다.

여기서 주의해야할 점은 erase를 사용해 지우면 기존 iterator가 가리키는 값이 없어진 것이기 때문에

지우기 전에 미리 iterator를 한 칸 왼쪽으로 옮겨주는 작업이 필요하다.

 

이 부분에 대한 함수는 removeDominated 와 registed 입니다!