[S2] 생태학 : Java : 4358

문제

4358번: 생태학

 

---

 

 

 

 

 

 

문제 접근

1초의 시간이고, 입력 케이스의 최대는 백만개이므로 최대 O(nlogn) 알고리즘으로 풀어야 겠다고 생각했다.

중복값 입력이 허용되고 그 중 전체 나무 중 차지하는 비율을 찾아야 되기 때문에 한 번 루프가 끝났을 때 그 나무가 나온 횟수를 찾아야 된다고 생각했다! 또한 문제의 핵심은 중복되는 자료가 나왔을 때 얼마나 빠르게 찾아 값을 변경 시키는 것이기 때문에 찾는 것에 시간 복잡도가 O(1)인 해쉬맵을 이용해야겠다고 생각했다.

---

 

 

 

 

 

 

문제 풀이

1. 입력 케이스를 입력 받을 때, 해쉬맵을 이용해 횟수를 갱신해가면서 <나무이름, 나온 횟수> 해쉬맵을 완성한다.

2. 오름차순 정렬을 해야하므로 해쉬맵의 키 리스트를 이용하여 정렬한다.

3. 정렬된 키 순서대로 1에서 생성한 해쉬맵을 이용하여 비율을 계산하고 출력한다.

---

 

 

 

 

 

 

알아야 하는 개념

테스트 케이스의 끝 입력 받기

테스트 케이스의 개수가 안 정해져있을 때는 문자열의 끝인 EOF를 인식하여 끝내야 한다. BuffereReader에서 readLine()으로 한 줄 입력을 가져올 때 null 값이면 EOF이다. 

+ 근데 왜인지 인식하지 못한다! 그래서 사용자가 빈줄을 입력할 때를 알아내는 isEmpty() 함수를 이용한다.

 

List 정렬 

ArrayList를 정렬하는 방법은 2가지가 있다. 

• Collections.sort()

 List<String> keys = new ArrayList<>(hash.keySet());
 
 // 오름차순 정렬
 Collections.sort(keys);
 
 // 내림차순 정렬
 Collections.sort(keys, Collections.reverseOrder());

 

• List.sort() - Java 8 이후

 List<String> keys = new ArrayList<>(hash.keySet());
 
 // 오름차순 정렬
 keys.sort(Comparator.naturalOrder());
 
 // 내림차순 정렬
 keys.sort(Comparator.reversOrder());

 

 

소수 포맷팅

String.format("%.4f", ratio);

 

---

 

 

 

 

코드 - Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class k_yujin {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<String, Integer> hash = new HashMap<String, Integer>();
        String input;
        int count = 0;

        // 테스트 케이스가 끝날 때까지 루프
        while ((input = br.readLine())!= null){
            if(input.isEmpty()) break;
            count++;
            // 해쉬맵에 포함되어 있으면 카운트 +1
            if(hash.containsKey(input)){
                hash.put(input, hash.get(input)+1);
            }
            // 새로운 key로 카운트는 1
            else{
                hash.put(input,1);
            }
        }

        // 오름차순 정렬
        List<String> keys = new ArrayList<>(hash.keySet());
        keys.sort((s1,s2)-> s1.compareTo(s2) );

        // 정렬된 순서에 따라 비율 계산 후 출력
        for(int i=0; i< keys.size(); i++){
            double ratio = ((hash.get(keys.get(i))/(count*1.0)))*100;
            System.out.println(keys.get(i) +" " + String.format("%.4f", ratio));
        }
    }

}