[백준] 7785 회사에 있는 사람 - HashSet(해시셋) JAVA

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

7785번: 회사에 있는 사람

코드설명

HashSet(해시셋) 을 활용합니다.

 

출입기록의 수는 n입니다. n은 (2 <= n <= 10^6, 10만개) 입니다.

만약 hashset을 사용하지 않고 Enter와 Leave를 arr에 삽입햇다가 삭제하는방법으로 진행한다면, 최악의 경우(Leave만 10만개 발생하는경우, 실제로 Enter가 된 사람을 뺴주어야 하기 때문에) 10만개의 데이터를 10만개 순회해야합니다. 10^6 * 10^6 = 10^12 으로써, 1000억 입니다.

 

HashSet을 사용하여 데이터 조회 시간을 O(1)로 줄이고, 정렬에 걸리는 시간인 O(n log(n)) 이 걸립니다.

 

코드상에서는 조금 더 짧게 코드하기 위해서, 아래와 같이 생성자에 바로 hashset을 넣습니다.

ArrayList<String> arr = new ArrayList<String>(hashset);
//		for(String a : hashset) {
//			arr.add(a);
//			System.out.println(a+" ");
//		}

 

만약 Array 형태였을 경우에는, Arrays.asList(arr)로 넣으면 ArrayList로 자동변환됩니다. 

항상 짧게 코딩하여 실수를 줄이는것이 중요합니다.

물론 이떄 import arrays.에서 만드는 ArrayList는 완전히 ArrayList의 라이브러리를 받지 않습니다. 단순히, ArrayList에 array를 빠르게 넣고싶을떄 넣어야만 합니다. array를 이 방식으로 ArrayList로 변환하는것에는 여러 기능적인 제약이 있습니다.  ( array.asList를 통해 ArrayList를 만들시 array배열의 값이 바뀌면 참조값이기에 ArrayList에도 값에 영향이 있을 수 있기에 add와 삭제가 애초에 불가합니다. )

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	public static int N, K;
	public static HashSet<String> hashset = new HashSet<String>();
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			String str1 = st.nextToken();
			String str2 = st.nextToken();
			if(str2.equals("enter")) {
				hashset.add(str1);
			}
			else {
				hashset.remove(str1);
			}
		}
		
		ArrayList<String> arr = new ArrayList<String>(hashset);
//		for(String a : hashset) {
//			arr.add(a);
//			System.out.println(a+" ");
//		}
		Collections.sort(arr);
		for(int i=arr.size() - 1 ; i>=0 ; i--) {
			System.out.println(arr.get(i));
		}
	}
}