BOJ13414 수강신청

선행지식

map

문제

국민대학교에서는 매 학기 시작 전 종합정보시스템에서 수강신청을 한다. 매 수강신청마다 아주 많은 학생들이 몰려 서버에 많은 부하가 가기 때문에, 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정하였다. 새로운 관리 시스템은 다음과 같은 방식으로 동작한다.

수강신청 버튼이 활성화 된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다.
이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 누를 경우 대기목록의 맨 뒤로 밀려난다.
잠시 후 수강신청 버튼이 비활성화 되면, 대기목록에서 가장 앞에 있는 학생부터 자동으로 수강신청이 완료되며, 수강 가능 인원이 꽉 찰 경우 나머지 대기목록은 무시하고 수강신청을 종료한다.

위의 표는 최대 수강 가능 인원이 3명인 알고리즘 수업에 대해 6명의 학생이 수강신청을 진행한 모습이다. 버튼이 비활성화 된 후, 먼저 규칙 1을 적용하여 클릭을 2번 이상 한 학생의 중복된 대기목록을 삭제한다. 중복된 목록을 제거한 후, 맨 앞에서부터 최대 수강 가능 인원인 3명을 선정한다. 표의 맨 오른쪽에는 그 최종결과를 나타낸 모습이다. 이와 같은 방법을 이용하여 최종적으로 수강신청에 성공한 인원을 출력하는 프로그램을 작성하시오.

접근방식 1 (vector)

간단하게 vector에서 find를 이용하여 값을 찾을 수 없다면 vector에 값을 넣고, 아니라면 규칙 2에 따라서 전에 입력받은 값을 삭제하고 vector에 값을 넣는다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;
    string x;
    vector<string> a;
    cin >> n >> m;
    while (m--){
        cin >> x;
        auto it=find(a.begin(),a.end(),x);
        if(it==a.end()){
            a.push_back(x);
        }else{
            a.erase(a.begin()+(it-a.begin()));
            a.push_back(x);
        }
    }for(auto i=a.begin(); i!=a.begin()+n; i++){
        cout << *i << '\n';
    }
}

간단하지만 역시… 시간초과가 나왔다.
삭제가 느려서 그런 것 같았다.

접근방식 2 (unordered_map)

이번에는 map에 저장하고 그 저장한 값과 index를 vector에 저장하고 index에 따라 정렬을 한 후에 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
bool cmp(pair<string, int>& a, pair<string, int>& b){
    return a.second < b.second;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,cnt=0;
    string x;
    unordered_map<string, int> a;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> x;
        if(a.find(x)!=a.end()){
            a.erase(x);
            a.insert({x,i});
        }else{
            a.insert({x,i});
        }
    }vector<pair<string, int>> v(a.begin(), a.end());
    sort(v.begin(), v.end(), cmp);
    for(auto i : v){
        if(cnt==n)break;
        cnt++;
        cout << i.first << '\n';
    }
}