[Baekjoon Online Judge] 7785. 회사에 있는 사람 (C++, Java)

https://www.acmicpc.net/problem/7785

 

핵심

N은 최대 1,000,000이다.

leave 로그마다 모든 enter 로그를 일일이 찾는 방법을 사용했을 때,

만약 N/2개의 enter 로그가 연달아 나오고 그 다음 N/2개의 leave 로그가 연달아 나온다면

N/2개의 enter 로그를 N/2개의 leave 로그에 대해 탐색해야 하므로 O(N^2)의 시간복잡도를 갖는다. (시간초과)

 

따라서 탐색 시간을 줄여야 한다.

여러 방법이 있는데 나는 해시 자료구조를 사용하는 방법을 사용했다.

해시 자료구조의 탐색은 O(1)의 시간복잡도를 갖는다.

이를 활용하면 앞선 상황에서 O(N)의 시간복잡도를 갖는다.

Code (C++) with std::unordered_set

#include <iostream>
#include <unordered_set>

using namespace std;

unordered_set<string> s;

int main(){
    int n;
    cin >> n;
    
    while (n--) {
        string name, action;
        cin >> name >> action;
        if (action == "enter") {
            s.insert(name);
        } else {
            s.erase(name);
        }
    }
    
    vector<string> names(s.begin(), s.end());
    sort(names.begin(), names.end(), greater<string>());
    for (const string& name : names) {
        cout << name << '\n';
    }
}

Code (Java) with java.util.HashSet

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static final String ENTER = "enter";
//    static final String LEAVE = "leave";

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();


        int n = Integer.parseInt(br.readLine());

        HashSet<String> hs = new HashSet<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            String action = st.nextToken();
            if (ENTER.equals(action)) {
                hs.add(name);
            } else {
                hs.remove(name);
            }
        }

        TreeSet<String> ts = new TreeSet<>(Collections.reverseOrder());
        ts.addAll(hs);
        for (String name : ts) {
            sb.append(name).append('\n');
        }
        System.out.println(sb);
    }
}