[백준] 25192 인사성 밝은 곰곰이 - HashSet(해시셋) JAVA

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

25192번: 인사성 밝은 곰곰이

코드설명

HashSet을 활용합니다.

 

N<=100,000 이므로, 만약 최악의 경우에는 O(N*N) 의 시간복잡도가 걸린다면 100억의 연산이 필요해 시간초과가 발생합니다.

HashSet을 활용하여 조회시 O(1)의 시간이 걸리므로, 시간초과가 발생하지 않습니다.

코드

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

public class Main {
	public static int N, M;
	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 input = st.nextToken();
			
			if(input.equals("ENTER")) {
				hashset = new HashSet<String>();
			}
			
			else {
				if(hashset.contains(input) == false) {
					answer += 1;
					hashset.add(input);
				}
				
			}
		}
		
		System.out.println(answer);
	}
	
	
}