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

문제링크 : https://www.acmicpc.net/problem/7785

 

문제풀이

문제만 처음 보고서는 쉬운 문제인 줄 알았는데, 시간초과가 문제였다. (N <= 10⁶)

 

처음에는 ArrayList에 enter인 경우 추가, leave인 경우 삭제를 하였는데..

Array이기 때문에 이렇게 하면 매번 추가 삭제될 때마다 배열을 다시 생성한다는 소리가 된다...(왜그랬지)

 

그래서 TreeMap을 이용하여 구현하였다.

TreeMap은 생성할 때 정렬법을 정의해주면 데이터가 추가될 때마다 Key값에 따라 자동으로 정렬이 된다.

문제에서는 역순으로 출력하라고 되어있어서, 역순으로 정의를 해주었다.

 

enter이면 map에 값을 true로 추가, leave이면 map에 값을 false로 추가해주었다.

(같은 키를 가진 데이터가 추가되면 중복으로 추가되지 않고 value값이 대체된다.)

 

그리고 마지막으로 값이 true인 키값을 찾아 순서대로 출력해주었다.

 

소스코드

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Iterator;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class P7785 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		Map<String, Boolean> log = new TreeMap<>(Collections.reverseOrder());
		//List<String> names = new ArrayList<String>();
		while (n-- > 0) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);
			String name = st.nextToken();
			String inout = st.nextToken();
			if (inout.equals("enter")) {
				log.put(name, true);
			}
			else {				
				log.put(name, false);
			}
		}
		
		Iterator<String> iterator = log.keySet().iterator();
		while (iterator.hasNext()) {
			String name = iterator.next();
			boolean inout = log.get(name);
			if (inout) System.out.println(name);
		}
		
		br.close();
	}
}