빈도 정렬(Frequency Sort)

출처 : https://www.acmicpc.net/problem/2910

빈도 정렬이란 배열의 원소를 반복 횟수에 따라 내림차순으로 정렬하는 경우를 말한다.

이것을 해결하기 위해서 다양한 알고리즘 해결 방법이 존재하지만, C++ STL를 이용하여 간단하게 해결할 수 있다.

1. 입력되는 수가 제한되기 때문에 Pair를 이용하여 <Value, <Count, Index> > 배열을 생성한다.

- 이 경우 unordered_map를 사용하여 배열 사용을 용이하게 할수 있다.

2. 상기 배열의 Count와 Index 를 이용하여 입력될때의 순서와, 횟수를 증가시킨다.

3. Map 을 Vector로 변환하여 Sort함수를 이용한다.

- 연산자 오버로딩을 이용하여 Key가 아닌 Value Sorting을 구현한다.

4. Count 수만큼 Value를 출력한다.

Case 1 :

Input

12 3
1 2 3 1 2 3 1 2 3 1 2 3

output

1 1 1 1 2 2 2 2 3 3 3 3

Case 2 :

input

5 2
2 1 2 1 2

output

2 2 2 1 1