[BOJ / C++] 수강신청(13414)

문제

수강신청 : 문제 링크

문제 분석

• 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정했고, 새로운 관리 시스템은 다음과 같은 방식으로 동작한다.

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

• 이와 같은 방법을 이용하여 최종적으로 수강신청에 성공한 인원을 출력
  (입력의 첫 번째 줄에는 과목의 수강 가능 인원(K)과 학생들이 버튼을 클릭한 순서를 기록한 대기목록의 길이(L)이 주어진다. 두 번째 줄부터 L개의 줄에는 수강신청 버튼을 클릭한 학생의 한번이 클릭 순서대로 주어진다.)

• 탐색 및 정렬 시간을 줄이기 위해 unordered_map과 sort() 함수를 사용하는 방법을 채택하여 풀이

• <string, int> 형태의 unordered_map um을 초기화

• K, L을 순서대로 입력받고, L만큼 학번을 입력받고 그것을 um에 저장하는데 같은 학번이 입력되면 저장되는 정수가 그만큼 커지므로 우선순위에서 밀려난다. 입력이 끝나면 저장된 정수의 오름차순으로 정렬하기 위해 um을 vector vec에 pair 형태로 복사한다. sort() 함수에서 세번째 인자는 자료형을 의미하는데 compare 라는 bool 함수를 만들었는데, 이는 pair에서 int값을 비교하기 위함이다. 마지막으로 for loop을 사용하여 K와 vec 크기를 비교하여(vec이 K보다 작은 경우를 고려) 작은 수만큼 저장된 학번을 출력

unordered_map
map의 해시 테이블 버전이다. <unordered_map> 헤더에 다음과 같이 정의되어 있다.

template<
	typename _Kty,
    typename _Ty,
    typename _Hasher = std::has<_Kty>,
    typename _Keyeq = std::equal_to<_Kty>,
    typename _Alloc = std::allocator<std::pair<const _Kty, _Ty>>
class unordered_set;

map의 인터페이스를 모두 포함하고 있으며 추가적으로 HashTable 관련 인터페이들을 제공한다.

algorithm 헤더의 sort() 함수 사용법
void sort(T start, T end, Compare comp); //comp 인자가 공란이면 오름차순 정렬

• sort(v.begin(), v.end(), compare); // 사용자 정의 함수 사용
• sort(v.begin(), v.end(), greater<자료형>()); // 내림차순
• sort(v.begin(), v.end(), less<자료형>()); // 오름차순

풀이

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool compare(pair<string, int>& a, pair<string, int>& b) {
    return a.second < b.second;
}

int main()
{
    int K, L;
    unordered_map<string, int> um;
    string temp;
    
    cin >> K >> L;
    for(int i = 0; i < L; i++) {
        cin >> temp;
        um[temp] = i;
    }
    vector<pair<string, int>> vec(um.begin(), um.end());
    sort(vec.begin(), vec.end(), compare);
    for(int i = 0; i < min(K, (int)vec.size()); i++)
        cout << vec[i].first << "\n";
    return 0;
}