[백준/Java] 4358 생태학

🔗 문제 링크: https://www.acmicpc.net/problem/4358

🔍 고찰 과정

자료구조를 활용하여 특정 종이 입력한 빈도수를 저장하고 비율을 출력하는 방식을 생각했습니다.

사용한 자료구조는 TreeMap<String, Integer> 형태의 자료구조를 사용했는데 그 이유는 key 값을 사전순으로 정렬을 해야 하는데 TreeMap은 문자열을 key값으로 입력 시 key 값을 사전순으로 정렬을 해주는 기능을 가지고 있기 때문입니다.

 

참고로 Java에서 TreeMap 형태의 자료구조는 Red-Black Tree라는 자료구조를 사용하여 키를 정렬하는데 자가 균형 이진 탐색 트리의 일종으로 키의 삽입, 삭제, 탐색이 모두 O(log n) 시간 복잡도를 가지고 있습니다.

---

✏️ 코드

import java.io.*;
import java.util.Map;
import java.util.TreeMap;

public class Main {

    private static final String END_LINE = "\n";
    private static final String SPACE = " ";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        Map<String, Integer> map = new TreeMap<>();
        int totalCount = 0;
        String tree;
        while ((tree = br.readLine()) != null) {
            map.put(tree, map.getOrDefault(tree, 0) + 1);
            ++totalCount;
        }

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            sb.append(entry.getKey())
                    .append(SPACE)
                    .append(String.format("%.4f", (double) entry.getValue() * 100 / totalCount))
                    .append(END_LINE);
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

}