[백준] 2910번 : 빈도 정렬

문제

 

 

접근 방식

숫자의 등장 횟수가 가장 많은 순서대로 정렬해야 하고

같은 경우에는 처음 입력된 순서대로 유지해야 한다.

 

입력 순서를 유지하기 위해 LinkedHashMap을 사용해서 풀었는데

생각해보니 입력의 범위가 모두 int형이라 배열을 사용해도 되는 문제다.

 

순서와 숫자의 카운트만 신경 써서 정렬해주면 되는 문제라

구현 자체는 어렵지 않았다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		Map<Integer, Integer> sequence = new LinkedHashMap<>();

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			int key = Integer.parseInt(st.nextToken());
			sequence.put(key, sequence.getOrDefault(key, 0) + 1);
		}

		List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(sequence.entrySet()).stream()
			.sorted((o1, o2) -> {
				int ov = o1.getValue();
				int tv = o2.getValue();

				if (ov == tv) {
					return 0;
				} else if (ov > tv) {
					return -1;
				} else {
					return 1;
				}
			}).collect(Collectors.toList());

		for (Map.Entry<Integer, Integer> entry : entries) {
			int target = entry.getKey();
			int end = entry.getValue();

			for (int i = 0; i < end; i++) {
				sb.append(target).append(" ");
			}
		}

		System.out.println(sb);
	}
}