Algospot NERD2

문제 링크입니다: https://algospot.com/judge/problem/read/NERD2

문제 수를 x축, 라면 그릇 수를 y축으로 지정하여 좌표평면상의 점들로 사람들을 표현하면 이해하기 쉬운 문제였습니다.

A라는 사람이 B라는 사람보다 푼 문제 수도 적고, 라면 그릇 수도 적다면 NERD가 아니므로 좌표평면에서 직사각형 내부에 점이 있으면 NERD가 아닙니다.

그림으로 설명하자면,

예제에서 주어진 참가자 4명에 대해 좌표평면 위의 점으로 표현했을 떄 노란색 안에 점이 있다면 NERD가 아니라는 것을 확신할 수 있습니다!

또한, 지배당하지 않는 점들은 좌상단부터 우하단까지 계단식 모양을 형성하고, 이러한 특성을 갖기 떄문에 점이 추가되었을 떄 지배당하는지 여부를 쉽게 파악할 수 있습니다!

좌표평면의 점이 노란색에 포함되지 않는다면 지배당하지 않는다고 말하고 지배당하지 않는 점들을 저장하는 가장 쉬운 방법은 배열을 이용하는 것입니다.

하지만, N은 최대 50,000이고 배열을 이용하면 시간복잡도가 O(N^2)이기 떄문에 시간초과가 발생합니다.

따라서, 이진탐색트리 역할을 해주는 stl map을 이용해줍니다!(map은 key와 value를 first와 second에 저장해줍니다)

map이 익숙하지 않으시다면 다음 링크를 참고하세요!(https://ko.cppreference.com/w/cpp/container/map, 특히 lower_bound 함수를 주목해주세요)

#include <iostream>

#include <map>

using namespace std;

 

//현재 다른 점에 지배당하지 않는 점들의 목록을 저장

//coords[x]=y

map<int, int> coords;

//새로운 점 (x, y)가 기존의 다른 점들에 지배당하는지 확인한다

bool isDominated(int x, int y)

{

        //x보다 오른쪽에 있는 점 중 가장 왼쪽에 있는 점을 찾는다

        map<int, int>::iterator it = coords.lower_bound(x);

        //그런 점이 없으면 (x, y)는 지배당하지 않는다

        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;

        //반복문 불변식: it는 (x y)의 바로 왼쪽에 있는 점

        while (true)

        {

                 //(x, y) 바로 왼쪽에 오는 점을 찾는다

                 //it가 표시하는 점이 (x, y)에 지배되지 않는다면 곧장 종료

                 if (it->second > y)

                         break;

                 //이전 점이 더 없으므로 it만 지우고 종료한다

                 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 registered(int x, int y)

{

        //(x, y)가 이미 지배당하는 경우에는 그냥 (x, y)를 버린다

        if (isDominated(x, y))

                 return coords.size();

        //기존에 있던 점 중 (x, y)에 지배당하는 점들을 지운다

        removeDominated(x, y);

        coords[x] = y;

        return coords.size();

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 int N;

                 cin >> N;

 

                 coords.clear();

 

                 int result = 0;

                 for (int j = 0; j < N; j++)

                 {

                         int x, y;

                         cin >> x >> y;

 

                         result += registered(x, y);

                 }

                 cout << result << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략