[백준1764]HashSet과 ArrayList의 contains() 시간복잡도

 

 

간단해 보이지만 이 문제는 ArrayList의 contains() 메서드로 풀면 시간 초과가 난다.

HashSet이나 Map을 이용해서 풀면 풀린다.

 

왜일까?

 

 

 

자료구조	시간복잡도	메서드 구현 방식
HashSet의 contains()	O(1)	Hashmap을 기반으로 구현
ArrayList의 contains()	O(n)	indexOf()를 사용해서 contain여부를 결정

 

 

HashSet은 HashMap 기반으로 구현되어 있어서 contains 메서드를 실행할때 HashMap.contains() 메서드를 불러온다.
그러므로 시간복잡도는 O(1) 이다.

 

AllayList의 indexOf는 배열에 있는 항목의 수에 따라 시간복잡도가 결정되므로 O(n)이다.

 

 

⭐따라서 ArrayList를 사용해서 시간초과가 나거나, 효율성이 필요한 문제라면 HashSet을 사용하는 것이 좋다.⭐

 

 

https://www.baeldung.com/java-hashset-arraylist-contains-performance

 

 

 

문제 코드

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

public class Baek_1764 {
    public static void main(String[] args) throws 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());

        ArrayList<String> 듣보잡 = new ArrayList<>();

        StringBuilder sb = new StringBuilder();

        HashSet<String> 듣도못한사람 = new HashSet<>();
        for (int i = 0; i < N; i++) {
            듣도못한사람.add(br.readLine());
        }
        for (int i = 0; i < M; i++) {
            String 보도못한사람 = br.readLine();
            if (듣도못한사람.contains(보도못한사람)) {
                듣보잡.add(보도못한사람);
            }
        }

        Collections.sort(듣보잡);
        sb.append(듣보잡.size()).append('\n');

        for (int i = 0; i < 듣보잡.size(); i++) {
            sb.append(듣보잡.get(i)).append('\n');
        }
        System.out.println(sb);
    }
}

 

 

추가적으로 다음 포스팅에 컬렉션별로 시간 복잡도를 정리해 보았다.

 

컬렉션별 시간 복잡도(비공개)