[BaekJoon 13414번] 수강신청(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 
 

[문제 풀이 사이트]

 
 

13414번: 수강신청

 
 

[문제 설명]

 
 

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

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

 

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

 

[입력]

 
 

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

 
 

[출력]

 

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

 
 

[입출력 예]

 
 

입력	출력
3 8 20103324 20133221 20133221 20093778 20140101 01234567 20093778 20103325	20103324 20133221 20140101

 
 

[문제 풀이]

 
 
규칙1, 2번으로 인해 key, value로 저장되는 map 자료 구조를 사용했다.
key에는 '학번', value에는 'map에 삽입되는 순서'가 저장되도록 했다.

그리고 가장 먼저 수강 신청을 한 학생들을 가려내기 위해 map에서 vector로 자료 구조를 변경하였다.
vector는 pair<int, string> 형태로 int는 map에 삽입된 순서, string은 학번이 저장이 되도록 하였다.

변경된 자료 구조 vector를 sort 함수를 이용하여 '오름 차순 정렬'을 하였다.
map에 삽입된 순서를 기준으로 오름 차순 정렬이 되어 과목의 수강 신청 가능한 인원만큼만 학번을 출력하도록 코드를 작성했다.
 
 

[최종 코드]

 
 

[GitHub]

 
 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 
 

#include <bits/stdc++.h>
using namespace std;
map<string, int> m;
vector<pair<int, string>> vp;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int K, L; cin >> K >> L; // K : 수강 가능한 인원, L : 수강 신청한 학생 수
    int order = 0; 
    for(int i = 0; i < L; ++i) {
        string temp; cin >> temp;
        m[temp] = ++order;
    }

    for(auto iter = m.begin(); iter != m.end(); ++iter) {
        vp.push_back({iter->second, iter->first});
    }

    sort(vp.begin(), vp.end()); // 오름 차순 정렬
    int len = vp.size();
    for(int i = 0; i < len; ++i) {
        if(i < K) {
            cout << vp[i].second << '\n'; 
        } else {
            break;
        }
    }

    return 0;
}