문제 출처

단계별로 풀어보기 > 집합과 맵 > 회사에 있는 사람
https://www.acmicpc.net/problem/7785

문제 설명

첫째줄에 총 기록 수 N이 주어지고, 둘째 줄부터 사람 + 출근/퇴근 이 주어진다.
이 때, 기록이 전부 주어지고 난 후, 회사에 남은 사람을 출력하라

접근 방법

HashSet을 통해 기록을 저장한다. 단, enter 인 경우만 hashSet에 add하고, 이외에는 remove를 통해 HashSet에서 삭제한다.
HashSet을 정렬한 뒤, 역순으로 출력한다.

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

public class 회사에_있는_사람 {
    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 p = st.nextToken();
            String c = st.nextToken();

            if(c.equals("enter")){
                hs.add(p);
            } else {
                hs.remove(p);
            }
        }

        StringBuilder sb = new StringBuilder();

        ArrayList<String> result = new ArrayList<>(hs);

        Collections.sort(result);

        for(int i = result.size()-1; i >= 0; i--){
            sb.append(result.get(i)).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

Collections.sort(result, Collections.reverseOrder()) 하게 되면, 역순이 되는데, 이를 깜빡하고 넣지 않고 반복문을 통해 역순으로 출력했다.

시간복잡도는 N만큼 입력 및 출력을 하게 되므로(add, remove는 O(1) 이므로 제외) O(2N) -> O(N)의 시간 복잡도를 가진다.

문제푼 흔적