문제
나무 종 이름이 입력될 때, 각 종의 비율을 사전순으로 출력하라.
입력
나무 종 이름이 한 줄에 하나씩 주어진다.
출력
각 종의 이름과 비율을 사전순으로 소수점 넷째 자리까지 출력한다.
예제
| 입력 | 출력 |
|---|---|
Red Alder Ash Ash Red Alder | Ash 50.0000 Red Alder 50.0000 |
풀이
HashMap으로 종별 개수를 세고, 키를 정렬하여 비율을 출력한다.
- HashMap에 각 종의 등장 횟수를 기록한다
- 전체 개수를 센다
- 키를 사전순 정렬 후
(개수/전체)*100을 소수점 넷째 자리까지 출력한다
핵심 아이디어: HashMap으로 O(1) 카운팅 후, 키 정렬하여 비율을 계산한다.
코드
package day599;
import java.io.*;
import java.util.*;
public class Day550BOJ4358생태학 {
static HashMap<String, Integer> trees;
static int allCount;
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
trees = new HashMap<String, Integer>();
String str = br.readLine();
while (true) {
trees.put(str, trees.getOrDefault(str, 0) + 1);
allCount++;
str = br.readLine();
if (str == null || str.length() == 0) {
break;
}
}
Object[] keys = trees.keySet().toArray();
Arrays.sort(keys);
StringBuilder sb = new StringBuilder();
for (Object key : keys) {
String keyStr = (String) key;
int count = trees.get(keyStr);
double per = (double) (count * 100.0) / allCount;
sb.append(keyStr + " " + String.format("%.4f", per) + "\n"); // 소수점 4번 째 자리까지 출력
}
System.out.println(sb.toString());
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)