[BOJ 2910] 빈도 정렬

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

2910번: 빈도 정렬

 

문제가 어렵거나, 구현이 어려운 문제는 아니지만. 제출시 오류가 났다...

한참 오류난 포인트를 찾았는데.. 핵심은 

 

수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다. 이렇게 정렬하는 방법을 빈도 정렬이라고 한다.

'만약, ~~' 부터가 오류의 원인이다. 수열내 등장한 개수가 같다면. 먼저 등장한 숫자를 먼저 출력해줘야 하는 부분..

이것을 Sort rule에 추가하면 바로 해결됨.

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.StringTokenizer;

public class boj2910 {
	static int N, C;
	static class Node implements Comparable<Node>{
		int Num, Count, idx;
		public Node(int num, int count, int idx) {
			this.Num = num;
			this.Count = count;
			this.idx = idx;
		}
		@Override
		public int compareTo(Node o) {
			if(o.Count == this.Count) {
				return this.idx - o.idx;
			}
			return o.Count - this.Count;
		}
	}
	static HashMap<Integer, Node> hm = new HashMap<>(); 
	
	static long[] Num;
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/input_2910.txt"));
		long Start = System.currentTimeMillis();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		
		int n;
		for (int i = 0; i < N; i++) {
			n = Integer.parseInt(st.nextToken());
			if(hm.containsKey(n)) {
				Node nd = hm.get(n);
				nd.Count++;
				hm.put(n, nd);
			} else {
				hm.put(n, new Node(n, 1, i));
			}
		}
		
		ArrayList<Node> list = new ArrayList<>();
		for (Entry<Integer, Node> e : hm.entrySet()) {
			list.add(e.getValue());
		}
		
		Collections.sort(list);
		StringBuffer sb = new StringBuffer();
		for (Node node : list) {
			for (int i = 0; i < node.Count; i++) {
				sb.append(node.Num+" ");
			}
		}
		
		System.out.println(sb.toString());
	}

}