백준 2910번: 빈도 정렬 [정렬][Map] - Java

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

2910번: 빈도 정렬

728x90

LinkedHashMap을 사용하면 순서도 보장되며, 정렬도 할 수있다.

 

나는 그냥 HashMap과 ArrayList 2개를 이용해서 풀었다.

N이 1,000개 이기때문에 N^2를 하여도 시간초과가 나지 않을 거라고 계산...

 

 

728x90

 

int[] 와 Integer[]의 sort시에 stable 의 차이가 있다.

Integer[]를 비롯한 Object형식의 배열은 sort시에  입력순서가 먼저인 것이 먼저들어온다. (stable 하다!)

int, float와 같은 기본적인 데이터 형의 변수들은 unstable하다.

 

<Java 코드>

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.Comparator;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		
		ArrayList<Integer> seq = new ArrayList<Integer>(); 
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();	
		
		st = new StringTokenizer(br.readLine());
		for (int tc = 0; tc < N; tc++) {
			
			int num = Integer.parseInt(st.nextToken());
			
			if(!seq.contains(num))
				seq.add(num);
			
			if(map.containsKey(num))
				map.put(num, map.get(num)+1);
			else
				map.put(num, 1);
			
		}
		
		//정렬
		ArrayList<Integer> ans = new ArrayList<Integer>(seq); //복사
		
		Collections.sort(ans, new Comparator<Integer>() {
			
			@Override
			public int compare(Integer o1, Integer o2) {
				if(map.get(o1) > map.get(o2))
					return -1;
				else if(map.get(o1)== map.get(o2)) {
					if (seq.indexOf(o1) < seq.indexOf(o2))
						return -1;
					else
						return 1;
				}
				else 
					return 1;
			}
		});
		
		for (int i = 0; i < ans.size(); i++) {
			for (int j = 0; j < map.get(ans.get(i)); j++) {
				System.out.print(ans.get(i)+" ");
			}
			
		}
		
	}

}