BOJ 13414 수강 신청

www.acmicpc.net/problem/13414

13414번: 수강신청

 

1. 수강신청 버튼이 활성화된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다.
2. 이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 누를 경우 대기목록의 맨 뒤로 밀려난다.
3. 잠시 후 수강신청 버튼이 비활성화되면, 대기목록에서 가장 앞에 있는 학생부터 자동으로 수강신청이 완료되며, 수강 가능 인원이 꽉 찰 경우 나머지 대기목록은 무시하고 수강신청을 종료한다.

위 조건을 만족시키며 수강신청에 성공한 사람의 학번을 출력하면 된다.

 

처음엔 vector.erase 함수를 사용해서 풀어볼까 했지만 

 

 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목록의 길이 L(1 ≤ L ≤ 500,000)

 

vector.erase는 시간복잡도 O(N)을 가지기 때문에 for문을 두 번 사용하면 총 \(O(N^2)\)으로 시간 초과가 난다.

 

따라서 자료구조를 사용해야 되는데 pair형으로 자료를 저장할 수 있는 map을 사용했다.

 

	unordered_map<string, int> m;
	vector<pair<int, string>> ar;

	cin >> n >> k;
	
	for (int i = 0; i < k; i++) {
		cin >> s;
		m[s] = i;
	}

 

map과 unordered_map의 차이점을 문제를 풀며 처음 배웠다.

map은 자동으로 정렬하며 저장하지만 unordered_map은 정렬하지 않고 저장하기 때문에

삽입, 탐색, 삭제가 O(1)에 가능하다!!! 

 

그러나 그냥 사용하긴 힘들고 iterator와 함께 사용해줘야 편하다.

 

	for (auto i : m) {
		ar.push_back({ i.second,i.first });
	}

 

이후에 중복된 원소들을 거르고 int, string 형을 vector에 담아준다. 이후에 정렬해주고 출력하면 된다.

 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int n, k;
	string s;
	unordered_map<string, int> m;
	vector<pair<int, string>> ar;

	cin >> n >> k;
	
	for (int i = 0; i < k; i++) {
		cin >> s;
		m[s] = i;
	}

	for (auto i : m) {
		ar.push_back({ i.second,i.first });
	}
	sort(ar.begin(), ar.end());

	n = ar.size() < n ? ar.size() : n;
	for (int i = 0; i < n; i++) {
		cout << ar[i].second << '\n';
	}

	return 0;
}

 

n의 크기가 중복을 거르고 나온 벡터의 크기보다 클 수 있음에 주의해야 한다.