백준 - 집합과 맵 1764번 듣보잡 / ArrayList와 Set,Map의 시간복잡도

= 내가 접근한 방법 =

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 1. input
        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());

        // 2. 듣도 못한 사람 n명 추가
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            map.put(st.nextToken(), 0);
        }

        String name = "";
        List<String> result = new ArrayList<>();
        int resultNumber = 0;
        // 3. 보도 못한 사람 m명
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            name = st.nextToken();
            if (map.containsKey(name)) {
                result.add(name);
                resultNumber++;
            }
        }
        Collections.sort(result);
        sb.append(resultNumber).append("\n");
        for (String s : result) {
            sb.append(s).append("\n");
        }

        System.out.println(sb);

    }
}

이 코드는 정답 코드다.

 

내가 틀린 이유는 처음에 contains를 그냥 ArrayList에 저장해서 사용했는데, 이렇게 사용하면 시간 초과가 뜬다.

 

Set과 Map의 contains는 시간 복잡도가 O(1)이고,

 

List의 contains의 시간 복잡도는 O(n)이다.

 

이러한 사실을 이번 문제를 통해 알았고, 다음에 시간을 줄일 수 있는 최고의 방법만을 생각해서 풀어야겠다.