[백준] java 10815 숫자 카드

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

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

접근 과정 / 풀이 과정

이번 문제는 이해하기 어렵지 않았다. 카드의 나열을 총 두번 받는데 첫번째 받았었던 값이 두번째에도 들어오게 되면 해당 숫자를 1로 출력하고 아니라면 0으로 출력한다.
중복 값이 있는지 체크하는 것에서 해시메소드를 사용하면 쉽게 풀릴 것 같다.

public static void solvingProblem_HashSet() throws IOException{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
				
		int N = Integer.parseInt(bf.readLine());
		HashSet<Integer> set = new HashSet<>();		
		st = new StringTokenizer(bf.readLine() , " ");
		for(int i = 0; i < N; i++)
			set.add(Integer.parseInt(st.nextToken()));
		
		int M = Integer.parseInt(bf.readLine());
		st = new StringTokenizer(bf.readLine() , " ");
		for(int i = 0; i < M; i++)
			bw.write((set.contains(Integer.parseInt(st.nextToken())) ? 1 : 0 )+ " ");
		
		bw.flush();
	}

HashSet을 사용하여 두번 째 입력값들이 HashSet에 포함되어 있으면 1 아니라면 0을 출력하게 했다.

배운점

아마 HashSet뿐만 아니라 Map, table을 통해서도 충분히 풀 수 있을 것이다. 그럼 이 셋 중에서 어느 클래스가 더 속도가 빠를까?
궁금해진 나는 나머지 두개도 구현해보았다. HashMap과 Hashtable은 완전히 같다.

public class SetAndMap_10815 {	
	// 해시 Map
	public static void solvingProblem_HashMap() throws IOException{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
				
		int N = Integer.parseInt(bf.readLine());
		HashMap<Integer, Boolean> map = new HashMap<>();
		st = new StringTokenizer(bf.readLine() , " ");
		for(int i = 0 ; i < N; i++) 
			map.put(Integer.parseInt(st.nextToken()), true );
				
		int M = Integer.parseInt(bf.readLine());
		st = new StringTokenizer(bf.readLine() , " ");
		for(int i = 0; i < M; i++)
			bw.write((map.containsKey(Integer.parseInt(st.nextToken())) == true ? 1 : 0) + " ");
				
		bw.flush();
	}
    // 해시 Set
	public static void solvingProblem_HashSet() throws IOException{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
				
		int N = Integer.parseInt(bf.readLine());
		HashSet<Integer> set = new HashSet<>();		
		st = new StringTokenizer(bf.readLine() , " ");
		for(int i = 0; i < N; i++)
			set.add(Integer.parseInt(st.nextToken()));
		
		int M = Integer.parseInt(bf.readLine());
		st = new StringTokenizer(bf.readLine() , " ");
		for(int i = 0; i < M; i++)
			bw.write((set.contains(Integer.parseInt(st.nextToken())) ? 1 : 0 )+ " ");
		
		bw.flush();
	}
    // 해시 테이블
    public static void solvingProblem_Hashtable() throws IOException{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int N = Integer.parseInt(bf.readLine());
		Hashtable<Integer, Boolean> table = new Hashtable<>();
		st = new StringTokenizer(bf.readLine() , " ");
		for(int i = 0 ; i < N; i++) 
			table.put(Integer.parseInt(st.nextToken()), true );
		
		int M = Integer.parseInt(bf.readLine());
		st = new StringTokenizer(bf.readLine() , " ");
		for(int i = 0; i < M; i++)
			bw.write((table.containsKey(Integer.parseInt(st.nextToken())) == true ? 1 : 0) + " ");
		
		bw.flush();
	}
	
	public static void main(String[] args) throws IOException { 
		solvingProblem_HashSet();
	}
}

결과는 위와 같다. 위에서부터 HashSet , HashMap , Hashtable이다.

내 생각엔 Hashtable이 가장 느릴 줄 알았는데 의외로 메모리소비도 적고 가장 빨랐다.
Hashtable이 HashMap과는 달리 동기화를 지원해주어 속도가 더 느리다고 알고 있었는데 어떻게 된 것인지 알아보아야겠다.