[C++] 백준 13414번: 수강신청

문제 링크

13414번: 수강신청

문제 요약

수강신청을 하는데, 빨리 누른 학생 순으로 수강이 성공된다. 단, 대기열에 들어온 상태에서 다시 수강신청을 누르는 경우, 대기열의 맨 뒤로 밀려나게 된다. 버튼을 누른는 순서가 주어질 때, 수강에 성공하는 학생들을 순서대로 출력해야 한다.

접근 방법

입력이 50만이고, 제한시간이 1초이기 때문에 트리맵을 사용하면 시간이 애매할 것이라고 생각했습니다. 따라서 해시맵을 사용했습니다. 입력을 받으며, 이미 맵 안에 있는 경우에는 갱신을 해주고, 없는 경우에는 맵에 삽입을 해줍니다. key는 문자열, value는 int로 해줍니다. value는 몇번째 입력이었는지를 의미합니다. 그리고 맵 내의 모든 원소를 벡터에 저장해준 뒤에, value를 기준으로 오름차순으로 정렬합니다. 마지막으로, min(k, 벡터의 크기)까지만 출력을 해주면 됩니다. 실수를 많이해서 여러 번 틀린 문제였습니다.

코드

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int k, l;
	cin >> k >> l;

	unordered_map<string, int> student;
	for (int i = 0; i < l; i++) {
		string number;
		cin >> number;
		student[number] = i;
	}

	vector<pair<string, int>> v;
	for (auto& i : student)
		v.push_back(i);

	sort(v.begin(), v.end(), compare);
	for (int i = 0; i < min(k, (int)v.size()); i++)
		cout << v[i].first << '\n';
	return 0;
}