BOJ 13414번: 수강신청

문제

입력

입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목록의 길이 L(1 ≤ L ≤ 500,000)이 주어진다. 두 번째 줄부터 L개의 줄에는 수강신청을 버튼을 클릭한 학생의 학번이 클릭 순서대로 주어진다. 학번은 8자리의 숫자로 이루어져 있다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 수강신청 관리 시스템의 규칙을 적용한 후 수강신청에 성공한 인원의 학번을 한 줄에 1개씩 출력한다.

---

문제 풀이1 - 시간 초과

벡터 사용

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

/*
존재하면 갱신, 없으면 삽입
*/

vector<int> v;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int k, l, num, i, j;
	cin >> k >> l; // 수강가능인원, 대기목록길이

	for (i = 0; i < l; i++) {
		cin >> num;
		if (i != 0) {
			for (j = 0; j < v.size(); j++) {
				if (v[j] == num) {
					v.erase(v.begin() + j); // j번째 원소 삭제
				}
			}
		}
		v.push_back(num);
	}

	for (i = 0; i < k; i++) {
		cout << v[i] << '\n';
	}

	return 0;
}

문제 풀이2 - 맞았습니다!

#include <iostream>
#include <unordered_map> // 정렬 없는 map (해시 맵)
#include <vector>
#include <algorithm>
using namespace std;

/*
존재하면 갱신, 없으면 삽입
*/

unordered_map<string, int> um; // key: 학번 value: 번호
vector<pair<string, int>> v; // value 정렬 위한 벡터

bool compare(const pair<string, int>& a, const pair<string, int>& b) { // value로 정렬
	return a.second < b.second;
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int k, l, i;
	string str;
	cin >> k >> l; // 수강가능인원, 대기목록길이

	for (i = 0; i < l; i++) { // 입력
		cin >> str;
		um[str] = i;
	}

	for (auto& i : um) { v.push_back(i); } // 벡터 삽입

	sort(v.begin(), v.end(), compare);
	for (i = 0; i < min(k, (int)v.size()); i++) { cout << v[i].first << '\n'; }

	return 0;
}