[백준 13414번] [Map] 수강신청

Approach

1번 조건 때문에 기존에 대기열에 존재하는지 여부가 굉장히 중요하다는 것을 알 수 있다.

왜냐하면 대기열 Set에 존재하는 상황에서 이후의 query가 들어오게 되면 나중의 순서로 재배정되기 떄문이다.

이 지점에서 기존의 대기열을 set으로 관리하여 존재하는지 여부를 관리하면 된다는 생각을 할 수 있다.

 

다만, 문제의 요구사항 중 하나는 대기열의 성공순서를 고려해야하는 상황이므로 어느 타이밍에 대기열에 등장했는지를 파악하는 것이 중요하다. 즉, 어느 타이밍에 대기열에 들어왔는지를 반영하기 위해서 Set보다는 Map 자료구조가 적합하다는 것을 알 수 있다. 그러나, key가 학번이므로 Map이 내림차순으로 정렬된다는 것을 활용항 수 없다. 따라서 Map을 2개 만듦으로서 이 문제를 해결해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int main(void){
    fastio;
    int k, l;
    map<string, int> s_1;
    map<int, string> s_2;
    cin >> k >> l;

    for(int i = 1; i <= l; i++){
        string v;
        cin >> v;
        if(s_1.find(v) != s_1.end()) s_2.erase(s_1[v]);
        s_1[v] = i;
        s_2[i] = v;
    }
    int count = 1;

    for(map<int,string>::iterator it = s_2.begin(); it != s_2.end(); it++){
        cout << it -> second << "\n";
        if(count == k) break;
        else count++;
    }
    return 0;
}