[백준] 1764 : 듣보잡 JAVA 풀이

듣도 못한 사람의 명단과 보도 못한 사람의 명단이 주어질 때

'듣도 보도' 못한 명단을 구해야 한다.

 

듣도 못한 사람을 ArrayList에 저장한 뒤, ArrayList.contains()로 보도 못한 사람이 포함된 경우에만

새로운 ArrayList에 저장하고 출력하려고 했지만 시간초과가 나왔다.

System.out.print를 너무 많이 호출해서인가하고 StringBuilder로 바꿔봐도 결과는 시간초과였다.

 

검색해보니 ArrayList.contains()는 O(n)이 걸리는 게 문제였던 것 같다.

HashSet의 contains() 메소드는 O(1)이 걸린다고 해서

듣도 못한 사람을 HashSet에 저장하고 그중에서 보도 못한 사람이 있는지 검사하는 방식으로 바꿨다.

 

1. N과 M을 입력받는다.

2. N명의 듣도 못한 사람의 명단을 입력받아 HastSet에 저장한다.

3. M명의 보도 못한 사람의 명단을 입력받고, HaseSet에 포함되어 있는 사람(= 듣도 보도 못한)이 있다면 ArrayList에 저장한다.

4. 듣도 보도 못한 사람의 명단이 저장된 ArrayList를 정렬하고, 인원수, 명단을 출력한다.

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

class Main {
	public static void main(String[] args) throws IOException
	{		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		HashSet<String> set = new HashSet<>();
		ArrayList<String> list = new ArrayList<>();
		
		for(int i=0;i<N;i++) {
			set.add(br.readLine());
		}
		
		for(int i=0;i<M;i++) {
			String str = br.readLine();
			if(set.contains(str)) {
				list.add(str);
			}
		}
		
		list2.sort(null);
		
		StringBuilder sb = new StringBuilder();
		
		sb.append(list.size()).append('\n');
		
		for(int i=0;i<list.size();i++) {
			sb.append(list.get(i)).append('\n');
		}
		System.out.print(sb);
	}
}