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

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

푸는데 시간이 오래 걸렸다.. 코로나 걸려서 집중력도 떨어지고 오랜만에 푸니까 잘 안풀린다.. ㅠ

unordered_map or undordered_set 같은 경우 내가 집어 넣은 순서대로 출력을 꺼낼 수 있다고 생각했는데 실제로는 넣은 순서대로 출력이 나오지 않고 해쉬 테이블 안에서 값을 꺼내므로 랜덤한 값이 출력되게 된다. 따라서 이 문제를 풀기위한 핵심은 unordered_map을 사용하여 학번과, 숫자(들어온 순서) 를 pair자료형을 통해서 받고 숫자를 기반으로 정렬하는 방법이 최선이란것을 깨달았다. 아래 두개의 풀이를 참고했다.

#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;

아래는 바킹독님 문제풀이다.

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

using namespace std;

#define X first
#define Y second


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

	int k, l;
	cin >> k >> l;
	unordered_map<string, int> signup{};

	for(int i=0; i<l; i++)
	{
		string student_num;
		cin >> student_num;
		
		if (signup.find(student_num) != signup.end())
		{
			signup.erase(student_num);
			signup[student_num] = i;
		}
		else
		{
			signup[student_num] = i;
		}
		
	}
	vector<pair<string, int>> slist(signup.begin(), signup.end());

	sort(slist.begin(), slist.end(), [](auto& a, auto& b) { return a.Y < b.Y; });

	int en = min(k,(int)slist.size());

	for (int i=0; i<en;i++)
	{
		cout << slist[i].X << '\n';
	}

	return 0;
}