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

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

7785번: 회사에 있는 사람

 

 

 

 

 

문제

• 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 10^6)
• 각 사람의 이름이 주어지고 "enter"인 경우는 출근, "leave"인 경우는 퇴근
• 회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름
• 현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력

 

 

 

 

 

풀이

실버4 문제로 막 알고리즘 공부를 시작할 2년 전에 이 문제를 풀었다가 시간 초과로 틀렸었다. 2년이 지난 지금 문제를 다시 풀어봤는데, 시간 초과가 난 이유를 바로 찾아 금방 해결할 수 있었다. (2년 사이에 실력이 늘었음을 실감하게 되었다!)

 

 

 

 

 

문제에 주어진대로 알고리즘을 정리해보면 다음과 같다.

 

1. 자료구조에 enter인 경우에는 삽입하고, leave인 경우에는 제거하고

2. 역순으로 정렬하여

3. 정렬된 자료구조를 순회하며 한 명씩 출력

 

 

 

보통 들어온 순서대로 삽입하고, 중간에서 제거 가능한 자료구조를 생각하면 List를 떠올린다. 그래서 2년 전의 나도 ArrayList로 구현했지만 시간초과를 맞게 되었다. 당시에는 자료구조 별 수행시간에 대해 잘 모를 때라 알고리즘은 맞은 것 같은데, 왜 틀린 건지 몰랐다.

 

 

 

• 큰 입력값 : (2 ≤ n ≤ 10^6) 

 출입 기록의 수가 최대 10의 6승 = 백만이다. 알고리즘을 구현했을 때, O(n^2)이상의 시간이 걸린다면 시간초과가 나게 된다. n개의 출입 기록을 순회하면서 삽입과 제거를 하는 데 n미만의 시간이 걸려야 한다. 자료구조 별 삽입과 제거 연산을 수행하는 데 걸리는 시간이 다르므로 자료구조를 고려해야 한다!

 

 

• 자료구조 별 수행 시간 : ArrayList VS HashSet

 ArrayList는 삽입에 O(1), 중간 원소 제거에 O(n)의 시간이 걸린다. 문제에서 삽입 연산은 괜찮은데, 제거 연산이 O(n)이기 때문에 시간 초과가 났을 것이다.

 

그럼 자료구조 중, 중간에서 제거하는 연산에서 O(1)만큼의 시간이 걸리는 자료구조를 찾아야 한다. 생각나는 자료구조는 HashMap, HashSet, Queue, Stack (상수시간이 걸리지만 중간에서 삭제할 수 없다) 이다.

 

HashMap, HashSet 중 어떤 자료구조를 써야할까? 문제를 자세히 읽어보면, '회사에는 동명이인이 없다'가 있다. 즉, 중복을 허락하지 않는다는 것이다. 둘 중 중복을 허락하는 자료구조를 선택하면 HashSet이다. HashMap은 key와 value로 구성이 되고, key 값만 겹치지 않는다면 value는 중복될 수 있다.

 

HashSet은 삽입에 O(1), 제거에 O(1)의 시간이 걸린다. 따라서 시간 초과의 문제를 해결하는 데 적합한 자료구조이다.

 

 

 

• HashSet 정렬

HashSet 정렬을 위해서는 ArrayList로 변환한 다음에 ArrayList를 정렬해야 한다.

 

 

 

 

 

코드

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

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());
		
		HashSet<String> set = new HashSet<>();
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(),  " ");
			String name = st.nextToken();
			String statement = st.nextToken();
			
			if(statement.equals("enter")) {
				set.add(name);
			} else {
				set.remove(name);
			}
		}
		
		//정렬
		List<String> list = new ArrayList<String>(set);
		Collections.sort(list, Collections.reverseOrder());
		
		//출력
		StringBuilder sb = new StringBuilder();
		
		for(String str : list) {
			sb.append(str + "\n");
		}
		
		System.out.println(sb);
	}

}

 

 

 

 

 

결과

 

 

 

 

 

배운점

• HashSet
  • 수행시간 : 삽입O(1), 제거O(1)
  • 정렬 : List<String> list = new ArrayList<String>(set);
• 리스트 내림차순 정렬 : Collections.sort(list, Collections.reverseOrder());