[CLASS 3: 구현] 백준 1764 듣보잡

1764번: 듣보잡

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

 

# 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        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());
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(br.readLine());
        }
        ArrayList<String> result = new ArrayList<>();
        for (int j = 0; j < m; j++) {
            String input = br.readLine();
            if (set.contains(input)) {
                result.add(input);
            }
        }
        Collections.sort(result);
        sb.append(result.size()).append("\n");
        for (String ele : result) {
            sb.append(ele).append("\n");
        }
        System.out.print(sb);
        br.close();
    }
}

• 듣도 못한 사람을 set에 담고, 겹치는 원소를 result에 추가한다.
• 처음에 ArrayList를 사용해 듣도 못한 사람을 담았는데 시간초과가 발생했다.
• 시간초과를 해결하려면 HashSet을 사용해야한다.
• 왜냐하면 ArrayList의 contains()는 O(n)이지만, HashSet의 contains()는 O(1)이기 때문이다. ArrayList는 indexOf()를 사용해서 contain여부를 결정하고, HashSet은 map을 기반으로 구현되기 때문이라고 한다.