백준 7785번 : 회사에 있는 사람 [Java]

🎁 문제 링크

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

7785번: 회사에 있는 사람

🎁 문제 설명

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

🎁 입출력 예시

🎁 코드

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Set<String> set = new HashSet<>();

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

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String key = st.nextToken();
            String input = st.nextToken();
            if ("enter".equals(input)) {
                set.add(key);
            } else if("leave".equals(input)) {
                set.remove(key);
            }
        }

        List<String> list = new ArrayList<>(set);
        list.sort(Comparator.reverseOrder());
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

    }
}

🎁 풀이

1) BufferedReader를 통해 입력을 받는다. 첫 번째 줄은 해당 조건의 갯수이다.

2) 2번째 줄부터 name을 받고, "enter"이면 set에 삽입하고, "leave"이면 set에서 삭제한다.

3) list에 set 인덱스를 넣어주고, 내림차순 정렬을 진행한다.

4) 진행한 후에 list의 인덱스 갯수만큼 출력을 진행한다.

🎁 Review & Point

▶ Point : 삭제 연산의 시간 복잡도

▶ Review

1) ArrayList를 이용하여 처음 문제를 진행했는데, 시간초과 발생

2) ArrayList.remove() 시에는 n만큼의 시간이 발생 -> 시간복잡도 O(n^2)

3) HashSet을 이용해서 값을 넣고 정렬 시에만 ArrayList 사용