문제

BOJ 13414, 수강신청

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 학번과 수강신청 순서가 주어진다. 수강 신청을 2번 이상 한 경우 순서는 가장 최근에 수강 신청을 한 순서로 밀려난다. 최대 수강 가능 인원의 학번을 파악하기 위해 학번과 수강신청 순서를 해시 자료구조를 사용하여 저장한 후 이를 순서로 오름차순 정렬한 뒤 수강 가능 인원까지 학번을 출력한다.
• C++에선 unordered_map, Java에선 HashMap 자료구조를 사용한다.

코드

시간복잡도

• $O(N\times\log_2N)$

C++

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int k, l;
	unordered_map<string, int> m;
	cin >> k >> l;
	for (int i = 1; i <= l; ++i) {
		string id;
		cin >> id;
		m[id] = i;
	}
	vector<pair<string, int>> v(m.begin(), m.end());
	sort(v.begin(), v.end(), [](auto& a, auto& b) {
			return a.second < b.second;
	});
	int count = 0;
	for (auto e : v) {
        if (count == k) break; 
		cout << e.first << '\n';
		++count;
	}
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());
        HashMap<String, Integer> hm = new HashMap<>();
        for (int i = 1; i <= l; i++) {
            String id = br.readLine();
            hm.put(id, i);
        }
        ArrayList<Map.Entry<String, Integer>> list = new ArrayList<>(hm.entrySet());
        Collections.sort(list, (a, b) -> a.getValue().compareTo(b.getValue()));
        int count = 0;
        for (Map.Entry<String, Integer> entry : list) {
            if (count == k) break;
            bw.write(entry.getKey() + "\n");
            count++;
        }
        bw.flush();
        bw.close();
        br.close();
    }
}