시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB106525818443354.220%

문제

위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다.

창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다.

만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.

이렇게 정렬하는 방법을 빈도 정렬이라고 한다.

수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.

입력

첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)

둘째 줄에 메시지 수열이 주어진다.

출력

첫째 줄에 입력으로 주어진 수열을 빈도 정렬한 다음 출력한다.

예제 입력 1

5 2
2 1 2 1 2

예제 출력 1

2 2 2 1 1

예제 입력 2

9 3
1 3 3 3 2 2 2 1 1

예제 출력 2

1 1 1 3 3 3 2 2 2

예제 입력 3

9 77
11 33 11 77 54 11 25 25 33

예제 출력 3

11 11 11 33 33 25 25 77 54
W3sicHJvYmxlbV9pZCI6IjI5MTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNDhcdWIzYzQgXHVjODE1XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MDRcdWIzMDBcdWQ1NWMgXHVkNTc0XHVjZWU0IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNTU0XHVkNjM4XHViOTdjIFx1YWU2OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTg4XHViMmU0LiBcdWFkZjggXHViYzI5XHViYzk1XHVjNzQwIFx1YmU0OFx1YjNjNFx1Yjk3YyBcdWM4NzBcdWMwYWNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViOWQwXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWQ2MDRcdWM2YjBcdWFjMDAgXHVhYzE1XHVjMGIwXHVjNzc0XHVjNWQwXHVhYzhjIFx1YmNmNFx1YjBiNFx1YjI5NCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHVkNjhkXHViNGRkXHVkNTg4XHViMmU0LiBcdWM3NzQgXHViYTU0XHVjMmRjXHVjOWMwXHViMjk0IFx1YzIyYlx1Yzc5MCBOXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NzRcdWFjZTAsIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWJhYThcdWI0NTAgQ1x1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM3OTBcdWM4ZmMgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YmU0OFx1YjNjNFx1YzIxY1x1YjMwMFx1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QsIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWI0NTAgXHVjMjE4IFhcdWM2NDAgWVx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBYXHVhYzAwIFlcdWJjZjRcdWIyZTQgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YjljZVx1Yzc3NCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFhcdWFjMDAgWVx1YmNmNFx1YjJlNCBcdWM1NWVcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHVkNjlmXHVjMjE4XHVhYzAwIFx1YWMxOVx1YjJlNFx1YmE3NCwgXHViYTNjXHVjODAwIFx1YjA5OFx1YzYyOCBcdWFjODNcdWM3NzQgXHVjNTVlXHVjNWQwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM4MTVcdWI4MmNcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YmU0OFx1YjNjNCBcdWM4MTVcdWI4MmNcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViZTQ4XHViM2M0IFx1YzgxNVx1YjgyY1x1Yzc0NCBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCZuYnNwO1x1YzkwNFx1YzVkMCBcdWJhNTRcdWMyZGNcdWM5YzBcdWM3NTggXHVhZTM4XHVjNzc0IE5cdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEsMDAwLCAxICZsZTsgQyZuYnNwOyZsZTsgMSwwMDAsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhNTRcdWMyZGNcdWM5YzAgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YmU0OFx1YjNjNCBcdWM4MTVcdWI4MmNcdWQ1NWMgXHViMmU0XHVjNzRjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTEwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU09SVCIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaXMgYSBncmVhdCBjb2RlIGJyZWFrZXIuIEhlIGtub3dzIGFueSBjaXBoZXIgaW4gdGhlIHdvcmxkIGNhbiBiZSBicm9rZW4gYnkgZnJlcXVlbmN5IGFuYWx5c2lzLjxcL3A+XHJcblxyXG48cD5IZSBoYXMgY29tcGxldGVseSB0aGUgd3JvbmcgaWRlYSB3aGF0IGZyZXF1ZW5jeSBhbmFseXNpcyBpcywgaG93ZXZlci48XC9wPlxyXG5cclxuPHA+SGUgaW50ZXJjZXB0ZWQgYW4gZW5lbXkgbWVzc2FnZS4gVGhlIG1lc3NhZ2UgY29uc2lzdHMgb2YgTiBudW1iZXJzLCBzbWFsbGVyIHRoYW4gb3IgZXF1YWwgdG8gQyBNaXJrbyBiZWxpdmVzIGZyZXFlbmN5IGFuYWx5c2lzIGNvbnNpc3RzIG9mIHNvcnRpbmcgdGhpcyBzZXF1ZW5jZSBzbyB0aGF0IG1vcmUgZnJlcXVlbnQgbnVtYmVycyBhcHBlYXIgYmVmb3JlIGxlc3MgZnJlcXVlbnQgb25lcy48XC9wPlxyXG5cclxuPHA+Rm9ybWFsbHksIHRoZSBzZXF1ZW5jZSBtdXN0IGJlIHNvcnRlZCBzbyB0aGF0IGdpdmVuIGFueSB0d28gbnVtYmVycyBYIGFuZCBZICwgWCBhcHBlYXJzIGJlZm9yZSBZIGlmIHRoZSBudW1iZXIgb2YgdGltZXMgWCBhcHBlYXJzIGluIHRoZSBvcmlnaW5hbCBzZXF1ZW5jZSBpcyBsYXJnZXIgdGhhbiB0aGUgbnVtYmVyIG9mIHRpbWUgWSBkb2VzLiBJZiB0aGUgbnVtYmVyIG9mIGFwcGVhcmFuY2VzIGlzIGVxdWFsLCB0aGUgbnVtYmVyIHdob2VzIHZhbHVlIGFwcGVhcnMgc29vbmVyIGluIHRoZSBpbnB1dCBzaG91bGQgYXBwZWFyIHNvb25lciBpbiB0aGUgc29ydGVkIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD5IZWxwIE1pcmtvIGJ5IGNyZWF0aW5nIGEgJnF1b3Q7ZnJlcXVlbmN5IHNvcnRlciZxdW90Oy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzLCBOICgxICZsZTsgTiAmbGU7IDEgMDAwKSwgbGVuZ3RoIG9mIG1lc3NhZ2UsIGFuZCBDICgxICZsZTsgQyAmbGU7IDEgMDAwIDAwMCAwMDApLCB0aGUgbnVtYmVyIGZyb20gdGFzayBkZXNjcmlwdGlvbi48XC9wPlxyXG5cclxuPHA+TmV4dCBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMgc21hbGxlciB0aGFuIG9yIGVxdWFsIHRvIEMsIG1lc3NhZ2UgaXRzZWxmLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIE4gbnVtYmVycywgdGhlIHNvcnRlZCBzZXF1ZW5jZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #3 3번