2910 : 빈도 정렬 - JAVA

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

 

말그대로 숫자의 출현 빈도에 따라 빈도가 많은 숫자를 앞에, 빈도가 적은 숫자를 뒤에 두게끔 정렬하는 문제이다.

나는 중복이 삭제되는 해시맵으로 해당 숫자의 등장 빈도를 파악했고

등장 빈도에 따라 정렬이 되도록 했다.

이외 등장 빈도가 같다면, 오름차순 정렬을 하도록 설정했다.

기존 배열과 복사용 배열을 모두 일반 배열로 뒀었는데, 정렬의 불편함이 있어서 Collections를 사용할 수 있는 Integer 배열 혹은 ArrayList를 사용하고자 했고, ArrayList를 사용하여 정렬을 하였다.

문제에서 원하는 정렬 알고리즘은 다음과 같다.

		Collections.sort(arr, (l1, l2) ->{
			if(hm.get(l1) == hm.get(l2)) {
				return cp.indexOf(l1) - cp.indexOf(l2);
			}
			else {
				return Integer.compare(hm.get(l2), hm.get(l1));
			}
		});

둘의 등장 빈도가 같다면 오름차순 정렬, 등장 빈도가 다르다면 등장 빈도가 높은것이 앞에 뜨도록 정렬 순서를 조정한다.

 

람다식을 쓰지 않은 형태는 다음과 같다.

Collections.sort(arr, new Comparator<ArrayList>() {
    @Override
    public int compare(ArrayList l1, ArrayList l2) {
        if (hm.get(l1) == hm.get(l2)) {
            return cp.indexOf(l1) - cp.indexOf(l2);
        } else {
            return Integer.compare(hm.get(l2), hm.get(l1));
        }
    }
});

소스코드는 다음과 같다.

정렬 방법만 알면 되는 매우 쉬운 문제이다.

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		ArrayList<Integer> arr = new ArrayList<>();
		ArrayList<Integer> cp = new ArrayList<>();
		HashMap<Integer, Integer> hm = new HashMap<>();
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i <n; i++) {
			arr.add(Integer.parseInt(st.nextToken()));
			cp.add(arr.get(i));
			hm.put(arr.get(i), hm.getOrDefault(arr.get(i), 0)+1);
		}
		//빈도 많은게 뒤에 오도록 설정
		Collections.sort(arr, (l1, l2) ->{
			if(hm.get(l1) == hm.get(l2)) {
				return cp.indexOf(l1) - cp.indexOf(l2);
			}
			else {
				return Integer.compare(hm.get(l2), hm.get(l1));
			}
		});
		Collections.sort(arr, new Comparator<ArrayList>() {
			@Override
			public int compare(ArrayList l1, ArrayList l2){
				if(hm.get(l1) == hm.get(l2)) {
					return cp.indexOf(l1) - cp.indexOf(l2);
				}
				else {
				return Integer.compare(hm.get(l2), hm.get(l1));
				}
			}
		});
		for(int i = 0; i < n; i++) {
			bw.write(arr.get(i) + " ");
		}
		bw.flush();
		bw.close();
		br.close();
	}
}