[BOJ] 백준 7785번 회사에 있는 사람 (Java)

#7785 회사에 있는 사람

난이도 : 실버 5

유형 : 자료구조 / Map

7785번: 회사에 있는 사람

▸ 문제

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.

회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

▸ 출력

현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

 

문제 풀이  

자료구조에 대한 개념을 물어보는 문제이다. 자료구조 List는 데이터가 정렬된 상태로 저장이 되어 탐색이 빠르지만 삽입/ 삭제면에서는 시간이 오래걸린다. 그에 반면 데이터를 포인터로 연결한 상태인 LinkedList나 해쉬테이블로 이뤄진 map,set과 같은 경우는 탐색은 느리지만 데이터 삽입/ 삭제에서는 더 좋은 성능을 가지고 있다.

 

따라서 해당 문제는 후자의 자료구조 Map을 사용해야 한다. 왜냐하면 "이름"과 "출결 상태"를 다루기 때문에 <key, value>에 상태 값을 넣어주면 되기 때문이다. 

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Map<String, Integer> checkList = new HashMap<>();
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String name = st.nextToken();
			String status= st.nextToken();
			if(checkList.containsKey(name)) {
				checkList.remove(name);
			}else {
				if(status.equals("enter")){
					checkList.put(name, 1);
				}
			}
		}

		StringBuilder sb= new StringBuilder();
		List<String> curList = new ArrayList<>(checkList.keySet());
		Collections.sort(curList,(a,b) -> b.compareTo(a));
		for(String s : curList) {
			sb.append(s+"\n");
		}
		System.out.println(sb.toString());
		
	}
}