[Algorithm] HashMap vs TreeMap

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

백준 20291 파일정리 실버3 문제에서 TreeMap을 적용해볼 기회가 있어서 TreeMap을 적용해봤다.

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));
        BufferedWriter bw = new BufferedWriter((new OutputStreamWriter(System.out)));
        int T = Integer.parseInt(br.readLine());

        HashMap<String, Integer> hm = new HashMap<>();

        while (T-- > 0) {
            String ext = br.readLine().split("\\.")[1];
            hm.put(ext, hm.getOrDefault(ext, 0) + 1);
        }
        List<String> list = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : hm.entrySet()) {
            list.add(entry.getKey());
        }
        Collections.sort(list);

        for (String k : list) {
            bw.write(k + " " + hm.get(k)+"\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

위와 같이 HashMap을 한 후 List로 키만 정렬 시켜서 결과를 반환했는데

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));
        BufferedWriter bw = new BufferedWriter((new OutputStreamWriter(System.out)));
        int T = Integer.parseInt(br.readLine());

        Map<String, Integer> hm = new TreeMap<>();

        while (T-- > 0) {
            String ext = br.readLine().split("\\.")[1];
            hm.put(ext, hm.getOrDefault(ext, 0) + 1);
        }
        List<String> list = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : hm.entrySet()) {
            bw.write(entry.getKey() + " " + entry.getValue()+"\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

다음과 같이 TreeMap을 통해 처리했을 때

다음과 같이 거의 100ms 빠르게 처리 가능했다.

 

HashMap은 정렬되지 않음 → O(1) 삽입이 빠르긴 하지만, 마지막에 키 리스트를 따로 뽑고 → O(n), 정렬을 수행해야 함 → O(n log n).

즉, 키가 많아질 수록 더 느려진다.

 

반면에 TreeMap은 내부적으로 Red-Black Tree 기반이라서, 데이터를 put()할 때마다 정렬 상태를 유지한다. → O(log n),

총 n개의 데이터에 대해서는 삽입 시 O(n log n).

따라서 entrySet()으로 바로 정렬된 순서를 얻을 수 있었다.