[백준]7785:회사에 있는 사람(JAVA)

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

7785번: 회사에 있는 사람

---

• 풀이방법[알고리즘]

퇴근 못 한 불쌍한 사람을 찾는 문제. 정렬 연습하려고 풀어보았다. ArrayList로 풀었더니 시간초과가 떴다. remove()는 O(n)이고 for문을 돌기 때문에 O(n^2)가 되어 시간초과가 된다고 한다. 아직 시간복잡도까지 계산해서 푸는건 너무 헷갈린당..... HashMap으로 leave 인 경우 map에서 삭제해주는 것으로 했다. HashMap의 키Set을 List로 받아 Collection.sort(lkeySet,Collection.reverseOrder())를 사용해 내림차순으로 정렬한 후 출력하면 끝!

public class Main {
    //B7785회사에있는사람_240416
    public static void main(String[] args) throws Exception{
        //로그가 주어졌을 때 회사에 있는구하기 -> 사전의 역순으로 구하기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        HashMap<String,String>list = new HashMap<>();
        String name="";
        String el="";
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            name=st.nextToken();
            el= st.nextToken();
            if(el.equals("enter")){
                list.put(name,"enter");
            }else{
                list.remove(name);
            }
        }
//        String[]names = list.toArray(new String[list.size()]);
//        Arrays.sort(names,Comparator.reverseOrder());
        ArrayList<String>keySet = new ArrayList<>(list.keySet());
        Collections.sort(keySet,Collections.reverseOrder());
        for(String str:keySet){
            sb.append(str).append("\n");
        }
        sb.trimToSize();
        System.out.print(sb);
    }//main
}//class