[2016 국민대 교내 경시대회] B. 수강 신청

BOJ 13414 수강 신청 (https://www.acmicpc.net/problem/13414)

이 문제는 C++ STL라이브러리의 map을 이용하므로,  map에 대해 잘 모르신다면, 아래글을 참고해주세요!

C++ STL라이브러리의 map, set(http://sarah950716.tistory.com/6)

해당 수업의 수강 가능 정원과 수강신청 버튼을 누른 학생의 학번이 순서대로 주어질 때, 수강신청에 성공한 학생들의 학번을 출력하는 문제입니다. (단, 동일한 학생이 수강신청 버튼을 두 번 이상 누른 경우 마지막에 누른 것만 유효처리됨)

이 문제는 단순한 구현 문제입니다. 단, 동일한 학생이 수강신청을 두 번 누른 경우, 마지막에 누른 것만 유효처리해야 하기 때문에 중복을 제거할 수 있는 자료구조를 이용해 구현하는 것이 편리할 것이라는 걸 알 수 있습니다. 또한, 수강신청 순서와 학번을 묶어서 관리해야 하기 때문에(나중에 정답을 출력할 때, 수강신청한 순서대로 출력해야 하기 때문) C++ STL의 map을 이용하면 해결할 수 있습니다. 

중복을 제거해야 하는 값은 '학번'이기 때문에 key로 학번, value로 수강신청 순서를 갖는 map을 정의해줍니다. 그리고, 수강신청 정보(학번과 수강신청 순서 쌍)를 하나씩 추가해줍니다. 그런데 만약, 이미 수강신청 버튼을 누른 학생이(map에 이미 추가된 정보) 또 수강신청 버튼을 눌러 다시 map에 추가하려는 경우 어떻게 해야 될까요? 이러한 경우, 아래와 같은 두 단계를 거쳐서 해당 학생의 정보를 갱신할 수 있습니다.

① map에 이미 존재하는 해당 학생의 정보를 삭제

② 해당 학생의 정보(나중에 누른 수강 신청 순서로)를 map에 추가

하지만 이렇게 구현하게 되는 경우, map의 정렬된 상태를 유지하기 위해 불필요한 시간이 들게 됩니다. key의 중복을 허락하지 않는 map의 특성상 이미 존재하는 key값을 갖는 pair를 map에 추가하는 경우, 해당 key값을 갖는 기존 pair의 value를 덮어쓰게 됩니다.  따라서, 위와 같이 삭제하고 추가해줄 필요 없이, 매번 수강신청 정보를 map에 추가해주기만 하면 됩니다.

마지막으로, 해당 문제의 예제를 보면 수강신청 순서대로 학번을 출력해야 하는 것을 알 수 있습니다. 하지만, map은 key(학번)값을 기준으로 정렬되어 있기 때문에 value(수강신청 순서)값을 기준으로 다시 정렬해 주어야 합니다. 이는 pair<수강신청 순서, 학번> 자료형을 갖는 vector와 stl의 sort함수를 이용하면 쉽게 구현할 수 있습니다. map전체를 돌면서 수강신청 정보를 vector에 모두 push_back 해주고 sort해주면 vector에는 수강신청 순서대로 정렬된 값들이 남게 됩니다.

혹시, 위와 같은 방식으로 구현했는데 런타임 에러가 발생한다면, 수강신청에 성공한 학생이 수강 가능 정원보다 작은 경우에 대해 고려해보시기 바랍니다.

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
#include <math.h>
#include <stdlib.h>
 
using namespace std;
 
int K, L;
map<int,int> A;
map<int,int>::iterator it;
vector<pair<int,int> > B;
 
int main()
{
    scanf("%d%d", &K, &L);
 
    for(int i=1; i<=L; i++)
    {
        int s; scanf("%d", &s);
        A[s] = i;
    }
 
    for(it=A.begin(); it!=A.end(); it++)
        B.push_back(make_pair(it->second, it->first));
 
    //수강 신청 순서 기준으로 정렬
    sort(B.begin(), B.end());
 
    //수강 신청에 성공한 학생이 수강 가능 정원보다 적은 경우를 고려해야 함
    int num = min(K,int(B.size()));
 
    for(int i=0; i<num; i++)
        printf("%08d\n", B[i].second);
}