[백준] 13414 수강신청 (C++)

문제

문제 분석

- 수강신청 정보를 담기 위해 map 자료구조를 사용한다.

- 이때, key의 순서대로 정렬할 필요가 없으므로 unordered_map을 사용한다.

- 이미 수강신청을 한 번 누른 적이 있는 경우 나중에 눌렀던 순서로 체크를 해야 한다.

- 처음 수강신청 버튼을 누른 경우 unordered_map에 값을 추가한다.

- 수강신청 순서대로(코드에서 pair의 second 값) 정렬하고, 정렬된 수강신청 순서에서 상위 K개의 학번만 수강신청한다.

- 위 조건을 구현 시 담는 것은 map으로 담아 중복을 제거하여 담고, 정렬할 때는 vector<pair>로 옮겨서 정렬해야 한다.

[주의사항]

제출 결과 출력 초과가 나오는 경우, 다음과 같은 예외처리를 빼먹은 것이다.

"한 사람이 여러 번 수강신청했다가 취소한다면?"

이 경우에는 K와 vector의 size 중 더 작은 것을 골라 그 갯수만큼만 출력을 해야 한다.

여기에서는 20203324 만 담기게 되므로 vector의 size는 1이고 K는 3이므로 더 작은 1개만 출력하여 20203324 가 출력되도록 해야 한다.

정답 코드

// 풀이 시간 : 26분 29초
// 주의 : set/map 사용 시 저장되는 순서가 입력 순서를 보장하지 않는다.
// 주의 : 한 사람이 여러번 수강신청 했다가 취소할 수 있다.

#include <iostream>
#include <unordered_map> // key 값에 따라 정렬할 필요가 없기 때문
#include <algorithm>
using namespace std;

unordered_map<string, int> um; // (학번, 수강신청 순서)

// 수강신청 순으로 오름차순 정렬
bool cmp(const pair<string, int>& p1, const pair<string, int>& p2) {
	if (p1.second != p2.second) return p1.second < p2.second; 
	return false;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int K, L;
	cin >> K >> L;
	// 학번 입력
	for (int i = 1; i <= L; i++) {
		string school_num;
		cin >> school_num;
		
		// 이미 수강신청을 한 번 눌렀던 경우
		if (um.find(school_num) != um.end()) {
			um[school_num] = i;
		}

		// 처음 수강신청 버튼을 누른 경우
		else {
			um.insert(make_pair(school_num, i));
		}
	}

	// 수강신청 순서대로 정렬
	vector<pair<string, int>> v(um.begin(), um.end());
	sort(v.begin(), v.end(), cmp);

	// 정렬된 수강신청 순서에서 상위 K개의 학번만 수강신청
	K = (K < v.size()) ? K : v.size(); // K와 vector의 size 중 더 작은 것을 K로 둔다.
	for (int i = 0; i < K; i++) {
		cout << v[i].first << "\n";
	}

	return 0;
}