[해시] BOJ 13417번 수강신청

https://www.acmicpc.net/problem/13414

13414번: 수강신청

- 문제파악

K명 수강가능한 강의에서 L명(L명 중에 같은 사람이 있을수도 있다)이 수강신청하려고 한다. 수강신청은 다음과 같은 규칙이 있다. 첫째 수강신청을 하면 대기열에 올라간다. 둘째 대기열에 올라간 사람이 다시 수강신청을 누르면 대기열에서 마지막으로 밀려난다. 세번째 대기열에 올라간 사람들중 순서가 가장 빠른 순으로 K명 수강신청이 완료된다. 수강신청 버튼을 누른 학생들의 학번이 차례대로 입력될 때 수강신청이 완료된 학생들을 출력하라.

 

- 정답

 

반례1. 학번을 정수로 받을 때

-> 01234567 과 같이 0이 앞에 있을때는 0이 사라지게 된다. 그러므로 학번은 문자열로 받는다

 

반례2. K = L 일 때 L의 모든 사람이 중복일 때

-> 예를 들어 2명 수강 가능한 강의에서 2명이 수강신청을 했는데 2명이 모두 01234567일 경우 2명을 출력할 수 없다.

 

unordered_set으로 문제에 접근했지만 왜인지 학번의 인덱스가 뒤로 붙지 않고 맨 앞으로 붙는 경우가 있다.

그래서 unordered_map으로 학번과 수강신청을 누른 순서를 받아서 vector로 한 번 정렬을 진행한 뒤에 출력을 했다.

 

#include "bits//stdc++.h"
using namespace std;

bool cmp(pair<string, int> a, pair<string, int> b)
{
	if (a.second < b.second) return true;
	return false;
}

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

	int n, m;
	cin >> n >> m;

	unordered_map<string, int> s;
	for (int i = 0; i < m; i++)
	{
		string str;
		cin >> str;

		if (s.find(str) != s.end())
			s.erase(str);

		s.insert({ str,i });

	}

	vector<pair<string, int>> vec(s.begin(), s.end());

	sort(vec.begin(), vec.end(), cmp);

	int nCnt = 0;
	for (auto a : vec)
	{
		if (nCnt++ == n) break;
		cout << a.first << "\n";
	}
		

}