[Baekjoon / C++] 13414. 수강신청

서준교·2023년 4월 6일

13414 C baekjoon

Algorithm

목록 보기

5/6

출처

13414번 - 수강신청

알고리즘 분류

구현
자료구조
해시를 이용한 집합과 맵

문제

풀이

해당 문제를 풀기 위해서 unordered map과 vector를 사용하였습니다. map의 데이터 탐색 속도는 $O(logN)$ , unordered map의 데이터 탐색 속도는 $O(1)$ 이기 때문에, 이 문제와 같이 대량의 데이터를 삽입해야 하는 경우 시간 측면에서 큰 이득을 볼 수 있습니다.

문제의 조건을 살펴보면, 수강신청 버튼을 빨리 누른 순서대로 대기목록에 들어가고, 클릭을 2번 이상 한 학생의 중복된 대기목록을 삭제한다. 입니다. 즉, 가장 마지막에 클릭한 순서를 기준으로 데이터를 정렬한다면 문제를 쉽게 풀 수 있습니다.
key를 학번으로 하고, 몇 번째에 마지막 클릭이 이루어졌는지에 대한 인덱스를 value로 하는 key-value 형태의 pair 값을 unordered map에 삽입합니다. 만약 기존의 map에 해당하는 학번이 이미 존재하는 경우, value 값을 업데이트합니다.

map에 위에 해당하는 로직을 통해서 데이터 삽입을 모두 마쳤다면, 데이터 정렬을 위해 map에 있는 pair 데이터를 vector로 복사합니다. 이 때, value 값을 기준으로 오름차순으로 데이터를 정렬해야 하기 때문에 정렬 규칙을 cmp 함수로 구현하였습니다.

값을 모두 복사했다면 sort 함수를 통해 정렬하고, K만큼 pair의 string값을 출력하면 됩니다. 이 때, 벡터의 크기가 K보다 작은 경우가 존재할 수 있으므로 해당 경우도 고려해야 합니다.

추가적으로 C++에서 출력시 개행을 하기 위해 endl과 "\n"을 사용하는데, endl의 경우에는 실행할 때마다 출력 버퍼를 비우는 flush 과정이 포함되어 있어 "\n"을 사용할 때보다 현저히 속도가 느립니다. 이 문제와 같이 많은 데이터를 개행을 통해 출력해야 하는 경우에는 endl을 사용할 경우 시간초과가 발생할 수 있으니, 이 부분도 꼭 확인해 보아야 하겠습니다.

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

#define pp pair<string, int>

using namespace std;

bool cmp(const pp& a, const pp& b)
{
	if (a.second == b.second) return a.first < b.first;
	return a.second < b.second;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	unordered_map<string, int> m;
	int K, L;
	cin >> K >> L;

	for (int i = 0; i < L; i++)
	{
		string student_num;
		cin >> student_num;
		if (m.find(student_num) != m.end()) // 클릭을 2번 이상 한 경우 
			m.find(student_num)->second = i;
		else
			m[student_num] = i;
	}

	vector<pp> v(m.begin(), m.end());
	sort(v.begin(), v.end(), cmp);
	
	for (int i = 0; i < v.size(); i++)
	{
		if (i == K) break;
		cout << v[i].first << '\n';
	}
}