문제

BOJ 7785, 회사에 있는 사람

핵심

• 입력의 크기가 $10^6$, 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 회사에 있는 사람의 이름을 알파벳 순으로 출력해야 한다. 해시 자료구조를 사용해 어떤 사람이 회사에 있는지 $O(1)$에 알아낸 후 이를 저장하여 정렬하도록 하자. 동명이인은 없으므로 C++ unordered_set, Java는 HashSet을 사용한다.

코드

시간복잡도

• $O(N\log_2N)$

C++

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	unordered_set<string> s;
	for (int i = 0; i < n; ++i) {
		string name, log;
		cin >> name >> log;

		if (log == "enter") {
			s.insert(name);
		} else
			s.erase(name);
	}
	vector<string> v(s.begin(), s.end());
	sort(v.begin(), v.end(), [](auto &a, auto &b) {
			return a > b;
	});
	for (auto c : v)
		cout << c << '\\n';
}

Java

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

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));
        int n = Integer.parseInt(br.readLine());
        HashSet<String> hs = new HashSet<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            String log = st.nextToken();
            if ("enter".equals(log)) hs.add(name);
            else hs.remove(name);
        }
        ArrayList<String> list = new ArrayList<>(hs);
        Collections.sort(list, (a, b) -> b.compareTo(a));
        for (var e : list)
            bw.write(e + "\\n");
        bw.flush();
        bw.close();
        br.close();
    }
}