[algospot] NERD2

문제링크 입니다

🚀 [NERD2] 문제 😊😊😊😊😊

대 성황이었던 지난 알고스팟 연간 모의고사 이후 프로그래밍 대회의 열기는 날로 뜨거워져 올해는 10만명이 넘는 사람들이 참가 신청을 할 것으로 예상되고 있습니다. 그러나 채점관을 할 자원 봉사자는 예년과 똑같이 5명뿐이라, 이 사람들을 대회에 다 참가시킬 수는 없습니다. 따라서 올해에도 참가 신청을 한 사람 중 진정한 프로그래밍 너드들만을 대회에 참가할 수 있도록 받아 주기로 했습니다.

종만의 새로운 이론에 따르면, 어떤 사람의 너드 지수는 다음 두 가지 값에 의해 결정됩니다.

• 알고스팟 온라인 채점 시스템에서 푼 문제의 수 p
• 밤 새면서 지금까지 끓여먹은 라면 그릇 수 q

이 이론에 따르면 어떤 참가 신청자 a 의 문제 수 pa 와 그릇 수 qa 를 다른 참가 신청자 b 의 문제 수 pb 와 그릇 수 qb 에 각각 비교했을 때, pa < pb, qa < qb 라면 참가 신청자 a 는 너드일 가능성이 없습니다. 조직위는 너드일 가능성이 있는 사람들만을 대회에 받아주기로 했습니다.

한 사람의 참가 가능 여부는 다른 사람들에 의해 결정되기 때문에, 대회에 참가할 수 있는 사람의 수는 새로운 사람이 참가 신청을 할 때마다 계속 바뀝니다. 예를 들어 다음과 같은 4명의 사람들이 순서대로 참가 신청을 했다고 합시다.

참가자	종만	재훈	효승	광규
문제 수	72	57	74	64
라면 그릇 수	50	67	55	60

종만과 재훈이 순서대로 대회 참가 신청을 하면 대회에 참가할 수 있는 사람의 수는 각각 1, 2 로 늘어나지만, 효승이는 문제 수도 라면 그릇 수도 종만보다 많으므로 효승이 참가 신청을 한 시점에서 종만은 더 이상 대회에 참가할 수 없습니다. 따라서 이 네 명이 참가 신청을 할 때마다 참가 가능자의 수는 1, 2, 2, 3으로 변합니다.

이렇게 각 사람이 참가 신청을 할 때마다 대회에 참가할 수 있는 사람들의 수가 어떻게 변하는지 계산하는 프로그램을 작성하세요.

🔑 [풀이]

문제 수를 x , 라면 그릇 수를 y로 생각하고 좌표평면에 그려본다면 이해하기 쉬운 문제 입니다.
예제를 예를들어 그림을 그려본다면 회색칸에 포함되지 않는다면 대회에 참가할 수 있게 되고,(이떄까지 참가자들에게 문제 수와, 라면 그릇 수가 포함되지 않기때문)
첫번쨰 참가자(72, 50)가 세번째 참가자(74, 55)에게 포함되므로 경기에 참가할 수 없게 되는 것을 확인할 수 있습니다.(빨간점) -> 제거한다.

이 문제를 vector를 이용하여 문제를 해결할려고 하였으나 N은 500000이므로 시간초과가 발생하였습니다.
조금 더 빠르게 해결하기 위해 map을 사용하였고, value 값보다 큰 수중 가장 작은 값을 돌려주는 lower_bound 를 활용해 시간을 단축하였습니다. map설명 참고

⌨️ 입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 참가 신청한 사람들의 수 N (1 <= N <= 50000) 이 주어집니다. 그 후 N 줄에 각 2개의 정수로 각 사람의 문제 수 pi 와 라면 그릇 수 qi 가 참가 신청한 순서대로 주어집니다 (0 <= pi,qi <= 100000) . 두 사람의 문제 수나 라면 그릇 수가 같은 경우는 없다고 가정해도 좋습니다. 입력의 양이 많으므로 가능한 빠른 입력 함수를 사용하는 것이 좋습니다.

🖥 출력

각 사람이 참가 신청을 할 때마다 대회 참가 자격이 되는 사람의 수를 계산한 뒤, 각 테스트 케이스마다 그 합을 출력합니다.

🖱 입력 예제

2
4
72 50
57 67
74 55
64 60
5
1 5
2 4
3 3
4 2
5 1

💻 출력 예제

8
15

💎 전체 코드는 다음과 같습니다.

//
//  NERD2.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/12/14.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
ifstream fin("NERD2.txt");

map<int,int> people;
bool isinclude(int x, int y){
    // 사람들 중 문제수가 가장 적은 곳을 가르킨다.
    map<int, int>::iterator it = people.lower_bound(x);
    // 사람들의 마지막을 가르키면 새로추가할 사람보다 문제수가 많은 사람이 없다는 뜻으로 무조건 포함되지 않는다.
    if(it == people.end()) return false;
    // 문제수가 가장 적은사람 보다 만약 y값(라면수) 가 많으면 추가 가능.
    return y < it->second;
}

void removeData(int x, int y){
    map<int, int>::iterator it = people.lower_bound(x);
    if(it == people.begin()) return;
    it--;
    while(true){
        if(it->second > y) break;
        if(it == people.begin()) {
            people.erase(it);
            break;
        }
        else{
            map<int,int>::iterator jt = it;
            jt--;
            people.erase(it);
            it = jt;
        }
    }

}
int registered(int x, int y){
    if(isinclude(x, y)) return people.size();
    removeData(x, y); // i 번째 신청자보다 문제수와 라면수가 적으면 참석 못하므로 그런 Data들 제거
    people[x] = y; // i 번째 신청자 추가.
    return people.size();
}
/*
// 답은 나오는데 시간초과.
int solve(vector<int>& problems, vector<int>& ramens){
    int sum = 1;
    people[problems[0]] = ramens[0];
    for(int i=1; i<problems.size(); i++){
        if(isinclude(problems[i], ramens[i])) continue;
        removeData(problems[i], ramens[i]); // i 번째 신청자보다 문제수와 라면수가 적으면 참석 못하므로 그런 Data들 제거
        people[problems[i]] = ramens[i]; // i 번째 신청자 추가.
        sum += people.size();
    }
    return sum;
}
*/
int main(){
    int test_case;
    fin >> test_case;
    for(int test=0; test<test_case; test++){
        int N;
        fin >> N;
        //vector<int> problems(N,0);
        //vector<int> ramens(N,0);
        int sum = 0;
        people.clear();
        for(int i=0; i<N; i++){
            int x,y;
            fin >> x >> y;
            //fin >> problems[i] >> ramens[i];
            sum += registered(x,y);
        }
        cout << sum << endl;

    }
    return 0;
}