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

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
        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> listen = new HashSet<String>();
        ArrayList<String> listenHear = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            listen.add(br.readLine());
        }

        while (m-- > 0) {
            String s = br.readLine();
            if (listen.contains(s))
                listenHear.add(s);
        }

        listenHear.sort((s1, s2) -> (s1).compareTo(s2));
        bw.write(listenHear.size()+"\n");

        for (String name : listenHear) {
            bw.write(name+"\n");
        }
        bw.flush();
        bw.close();
    }
}

처음에는 ArrayList로 풀었다가 시간초과가 나서 찾아보니
HashSet을 사용해야 풀 수 있는 문제였다.
HashSet의 contains()는 map을 기반으로 구현되어 O(1), ArrayList의 contains()는 indexOf()를 사용하기에 O(n)의 시간복잡도를 가진다!
포함여부를 묻는 문제에선 ArrayList보단 HashSet을 사용해야 한다는 깨달음을 얻은 문제였다.
또 Hash 문제를 여러개 풀어보며, HashSet과 HashMap의 차이도 알게 되었다.

[부록] HashSet과 HashMap의 차이

• HashSet : 해시 메커니즘을 사용하여 요소를 저장.
  성공적으로 추가되면 true를, 중복된 객체가 들어오면 false를 리턴
  HashMap에 비해 느림
• HashMap : key-value 형식의 데이터 저장. 중복 객체 마찬가지로 안받음
  unique key를 이용하여 데이터에 바로 접근하므로 HashSet에 비해서 빠름