[algospot] 너드인가, 너드가 아닌가? (c++)

출처 : algospot.com :: NERD2

algospot.com :: NERD2

풀이 방법

 

이 문제의 중요한 해결책은 문제 수와 라면 그릇 수를 좌표평면에 그려보는 것이다.

그려보게 되면 현재까지 등록되어 있는 너드들이 계단식으로 되어있다 즉 x 좌표가 작으면 y가 커야 하므로

오른쪽으로 갈수록 x좌표가 증가하고 y좌표는 감소하는 계단식이다.

여기서 새로운 사람이 추가되면 너드인지 아닌지 판별하기 위해 자신보다 x좌표가 큰 쪽만 보면 된다

왜냐하면 자신보다 x좌표가 작은 쪽은 x좌표가 작기 때문에 이미 x 좌표 하나를 봐도 큰 게 있기 때문에 너드가 될 수 있다.

자신보다 x좌표가 큰 쪽 중에서 가장 작은 점의 y 좌표와 자신의 좌표만 확인하면 된다. 

그 보다 x 좌표가 큰 점들은 어차피 자신의 x좌표보다 큰 점 중 가장 작은 점보다 y 좌표가 작기 때문에(계단식) 확인을 할 필요가 없다.

이렇게 너드인지를 판별하고 이 점에 의해서 너드자격을 박탈당한 점을 제거해주면 된다.

너드 제거는 자신보다 x 좌표가 작은 점들 중 가장 큰 점부터 x좌표가 작은 쪽으로 가며 y좌표가 자신보다 작으면 삭제를 하다 자신보다 y좌표가 큰 점이 나오면 반복문을 탈출하는 식으로 작성하면 된다.

#include <iostream>
#include <map>

using namespace std;

map<int, int> coords;

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;    
}

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) {
        // 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 registered(int x, int y) {
    //(x, y)가 이미 지배당하는 경우에는 그냥 (x, y)를 버린다
    if (isDominated(x, y)) return coords.size();
    //기존 점중 지배당하는 점들을 지운다
    removeDominated(x, y);
    coords[x] = y;
    return coords.size();
}

int main() {
    int c;
    cin >> c;
    while (c--) {
        coords.clear();
        int n;
        int sum = 0;
        cin >> n;
        while (n--) {
            int x, y;
            cin >> x >> y;
            sum += registered(x, y);
        }
        cout << sum << "\n";
    }
    return 0;
}

자료구조, 문법 정리

이 문제에서 map 자료구조를 사용하는데 이를 사용하면 모든 연산이 O(logn)만에 해결되기 때문에 배열을 사용하지 않았다. map은 균형 잡힌 이진 검색 트리이다.

코드에서 각 map을 순회하기 위해 iterator을 사용한다 iterator의 end는 마지막 원소의 다음 원소 즉 빈 원소를 가리킨다.

map.lower_bound(x) map에서 x 보다 큰 것 중 가장 작은 것의 iterator을 리턴한다.

map의 iterator을 사용한 원소 접근법 

it->first, it->second 형식으로 접근할 수 있다.