(Java) 백준 4358 생태학

문제 링크

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

나의 기록

✅ 알고리즘 분류 : 자료구조(Map), 문자열

✅ 성공 여부 : ✔

✅ 문제 난이도 : 실버2

✅ 체감 난이도 : Easy

접근 방법

이번에 알고리즘 문제를 공부하며 배운 TreeMap을 응용할 수 있는 문제를 풀어봤다.

출처 : https://m.blog.naver.com/PostView.nhn?blogId=baekmg1988&logNo=20194516618&proxyReferer=https%3A%2F%2Fwww.google.com%2F

TreeMap이란?

<key, value> 쌍으로 원소를 저장하는 Map 인터페이스에는 크게 3가지가 있다. HashTable, HashMap, 그리고 SortedMap.

HashMap은 우리가 가장 흔히 쓰는 해시테이블을 이용한 Map이고, TreeMap은 SortedMap을 상속받은 클래스이다.

 

TreeMap은 다음과 같은 특징들을 가지고 있다.

• Map의 장점인 빠른 검색, Tree의 장점인 정렬과 범위 검색의 장점을 가지고 있다.
• 데이터를 저장 시 정렬해야 하므로 저장 시간이 길다는 단점이 있다. 즉, 삽입 삭제가 잦을 경우는 좋지 않을 수 있다.
• 정렬된 데이터를 조회할 수 있으므로, 조회가 잦거나 정렬된 조회가 필요한 경우에는 HashMap보다 TreeMap이 좋다.

 

코드

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

public class bj4358_생태학 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        TreeMap<String, Integer> map = new TreeMap<>(); // 자동 정렬되는 map
        int cnt = 0; // 전체 입력 수

        // 입력
        while(true){
            String input = br.readLine();
            if(input == null || input.length() == 0) break;

            if(map.containsKey(input)){ // 이미 한 번 이상 나온 적 있는 종일 경우
                map.put(input, map.get(input) + 1);
            } else { // 처음 등장하는 종일 경우
                map.put(input, 1);
            }
            cnt++;
        }

        // 출력
        for(String key : map.keySet()){
            double value = (double)map.get(key) / (double)cnt * 100;
            System.out.println(key + " " + String.format("%.4f", value));
        }
    }
}