[JAVA]BOJ 2910, 빈도 정렬

이 문제에서 제일 중요한건, 등장하는 횟수가 같다면 먼저 나온 것이 앞에 있어야 한다는 것이다. 그것말고는 딱히 어렵지않다.

 

먼저 나온 것이 앞에 나오게 하기 위해 LinkedHashMap을 사용했다. HashMap과 유사하지만 들어온 순서를 기억한다.

 

1. 전에 푼 1302번과 유사하게 map에 값을 넣어준다.

2. value가 제일 큰 key를 찾아서 key를 value번 출력한다

3. map에서 출력된 key를 삭제한다.

4. 2번과 3번을 반복해서 map이 비면 끝낸다.

 

LinkedHashMap을 사용했기 때문에 value가 같더라도 먼저 들어온 set을 찾아준다.

 

---

아래는 전체 코드이다.

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

public class BOJ2910 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, C, i, key;
        String str;
        StringTokenizer st;
        Map<Integer, Integer> map = new LinkedHashMap<>();

        str = br.readLine();
        st = new StringTokenizer(str);
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        str = br.readLine();
        st = new StringTokenizer(str);
        for(i=0;i<N;i++){
            key = Integer.parseInt(st.nextToken());
            if(!map.containsKey(key)) // 처음 입력받은 수 일때
                map.put(key, 1);
            else
                map.put(key, map.get(key) + 1);
        }

        // 제일 큰 value 찾아서 key를 value번 출력 -> map에서 삭제 -> map 빌때까지 반복
        while(!map.isEmpty()){
            Map.Entry<Integer, Integer> maxEntry = Collections.max(map.entrySet(), Map.Entry.comparingByValue()); // 제일 큰 value 찾기

            for(i=0;i<maxEntry.getValue();i++)
                System.out.print(maxEntry.getKey() + " "); // 출력

            map.remove(maxEntry.getKey()); // 삭제
        }
    }
}