백준 온라인 저지 13414 수강신청

문제

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

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

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

입력

입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목록의 길이 L(1 ≤ L ≤ 500,000)이 주어진다. 두 번째 줄부터 L개의 줄에는 수강신청을 버튼을 클릭한 학생의 학번이 클릭 순서대로 주어진다. 학번은 8자리의 숫자로 이루어져 있다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 수강신청 관리 시스템의 규칙을 적용한 후 수강신청에 성공한 인원의 학번을 한 줄에 1개씩 출력한다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include <iostream> #include <map> #include <vector> #include <cstdio> #include <algorithm>   using namespace std; map<string, int> myMap; map<string, int>::iterator iter; vector<pair<string, int>> myVector;   bool cmp(const pair<string, int> &p1, const pair<string, int> &p2) {     return p1.second < p2.second; }   int main() {     int k, l;     string sNum;     scanf("%d%d", &k, &l);     for (int i = 0; i < l; i++) {         cin >> sNum;         myMap[sNum] = i + 1;     }     for (iter = myMap.begin(); iter != myMap.end(); iter++) {         myVector.push_back(make_pair((*iter).first, (*iter).second));     }     sort(myVector.begin(), myVector.end(), cmp);     for (int i = 0; i < min(k, (int) myVector.size()); i++)         cout << myVector[i].first << '\n';     return 0; }   Colored by Color Scripter

cs

 

풀이는 간단하다.

 

상대적인 순서만 알면 되기 때문에 22번째 줄을 통해서 학번에 해당하는 학생을 맨 뒤에 삽입하는 작업이 수행된다.

 

만약 그 학생이 앞에 존재하던 경우에는 앞에서 빼는 작업까지 수행되는 것이다.

 

그리고 벡터에 학번, 순서의 pair를 만들어서 삽입한다.

 

이 벡터를 순서에 따라 오름차순으로 정렬한 다음 벡터의 크기와 k 중 작은 값만큼 원소를 출력하면 된다.

 

처음에는 학번이 8자리라는 것을 생각해서 int로 선언했는데 틀렸고 string으로 고치니까 맞는 것으로 보아

 

학번 앞에 0이 붙는 경우가 있는 것 같다. 이 부분만 주의하면 될 것 같다.