[Java] BOJ 1764 듣보잡

문제 

문제 링크 https://www.acmicpc.net/problem/1764

• 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
• 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다.
• 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
• 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
• 듣보잡의 수와 그 명단을 사전순으로 출력한다.

아이디어

• 듣도 못한 사람이름을 hashmap에 저장하고 보도 못한 사람들을 입력받으면서 해당 문자열이 hashmap에 key값으로 저장되어 있으면 결과를 출력할 배열에 저장하고 없으면 저장하지 않았다. 
  
  

겪은 시행착오

• 처음에 시간초과가 자꾸 나서 뭐가 문제인가... 고민을 하며 반복문을 통해 같은 문자열이 있는지 찾던것을 ArrayList로 변환해서 contains로 바꿔보기도 하고 했지만 계속해서 시간초과가 났다..
• 고민하던 도중 hashmap의 key값을 활용하면 검색이 빠르다는 것이 생각이 났고 hashmap을 활용한 결과, 해결할 수 있었다...ㅜㅜ (더 좋은 방법이 있다면 알려주세요 ㅜㅜ)

시간초과... 무섭다...

'맞는거 같은데 왜 시간초과야!' 하는 나의 모습....ㅎ...

코드

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

public class BOJ1764 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 듣도 보도 못한 사람의 수
        int N = Integer.parseInt(st.nextToken());

        // 보도 못한 사람의 수
        int M = Integer.parseInt(st.nextToken());

        // 듣도 보도 못한 사람을 저장할 hashmap
        HashMap<String, String> no_l = new HashMap<>();

        // 듣도 보도 못한 사람을 저장할 배열
        List<String> result = new ArrayList<>();

        // 듣도 보도 못한 사람들을 입력받아 배열에 저장
        for(int i = 0; i < N; i++){
            String s = br.readLine();

            no_l.put(s, "1");
        }

        // 보도 못한 사람들을 입력받은 뒤,
        // 듣도 보도 못한 사람을 저장한 배열에 있으면 결과 배열에 저장
        for(int i = 0; i < M; i++){
            String s = br.readLine();

            if(no_l.containsKey(s)){
                result.add(s);
            }
        }

        // 정렬하기
        Collections.sort(result);

        sb.append(result.size() + "\n");

        for(int i = 0; i < result.size(); i++){
            sb.append(result.get(i) + "\n");
        }

        System.out.println(sb);
    }
}