1764. 듣보잡 (자바, Java)

이번에는 양쪽의 교집합을 이진탐색으로 구하는 문제.

그냥 HashMap 으로 풀었는데, 구글링해보니까 이진탐색으로 풀었던 경우도 보았다. 앞 집합에 있는 목록들로, 뒷 집합을 이진탐색하면서 찾아보는 식. 무언가 정공법으로 풀지 못해서 불-편했다. 하지만 이진탐색을 풀 기회는 앞으로도 많을 것이고, 뒷 문제는 이진탐색쪽으로 생각하기로 마음먹으며 그냥 넘어가기로 했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, 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());
		HashMap <String, Integer> map = new HashMap<>();
		
		for (int i=0; i<n; i++) {
			map.put(br.readLine(), 1);
		}
		
		List <String> ans = new ArrayList();
		StringBuilder sb = new StringBuilder();
		
		for (int i=0; i<m; i++) {
			String bo = br.readLine();
			map.put(bo, map.getOrDefault(bo, 0)+1);
			if (map.get(bo)==2) {
				ans.add(bo);
			}			
		}
		
		Collections.sort(ans);
		System.out.println(ans.size());
		
		for (int i=0; i<ans.size(); i++) {
			sb.append(ans.get(i) + "\n");
		}
		
		System.out.println(sb);
			
	}

}