[BOJ][JAVA] 2910번: 빈도정렬

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

2910번: 빈도 정렬

 

 

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int c = sc.nextInt();
		Integer[] input = new Integer[n];
		int[] seq = new int[c+1];
		Map<Integer, Integer> m = new HashMap<>();

		int idx = 1;
		for (int i = 0; i < n; i++) {
			int tmp = sc.nextInt();
			input[i] = tmp;
			if (!m.containsKey(tmp)) {
				m.put(tmp, 1);
				seq[tmp] = idx++;
			} else {
				int val = m.get(tmp);
				m.put(tmp, val + 1);
			}
		}

		Arrays.sort(input, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				if (m.get(o2) - m.get(o1) == 0) {
					return seq[o1] - seq[o2];
				} else {
					return m.get(o2) - m.get(o1);
				}
			}

		});

		StringBuilder sb = new StringBuilder();
		for (int i : input) {
			sb.append(i).append(" ");
		}
		System.out.println(sb);
	}
}

 

---

오답노트(푸는 동안 사고과정 및 개선점)

첫번째 시도는 Comparator 를 이용한 정렬이었다. 이렇게 하니까 빈도가 같은 경우 입력순 정렬이 아니라 똑같이 내림차순으로 정렬돼서 원하는 결과가 나오지 않았다. 

두번째 시도는 위치를 저장하는 배열을 하나 파는 것이었다.

->출력은 잘 되지만 메모리 초과 발생

-> 들어올 수 있는 값이 10억까지 있음. -> 당연히 메모리 초과 발생하게 됨 4byte * 10억 = 4기가

-> 이거도 map으로 묶어보자

 

 

---

정답코드

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int c = sc.nextInt();
		Integer[] input = new Integer[n];
		Map<Integer, Integer> m = new HashMap<>();
		Map<Integer, Integer> seq = new HashMap<>();

		int idx = 1;
		for (int i = 0; i < n; i++) {
			int tmp = sc.nextInt();
			input[i] = tmp;
			if (!m.containsKey(tmp)) {
				m.put(tmp, 1);
				seq.put(tmp, idx++);
			} else {
				int val = m.get(tmp);
				m.put(tmp, val + 1);
			}
		}
//		System.out.println(seq.toString());

		Arrays.sort(input, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				if (m.get(o2) - m.get(o1) == 0) {
					return seq.get(o1) - seq.get(o2);
				} else {
					return m.get(o2) - m.get(o1);
				}
			}

		});

		StringBuilder sb = new StringBuilder();
		for (int i : input) {
			sb.append(i).append(" ");
		}
		System.out.println(sb);
	}
}

 

순서를 저장하는 배열을 map으로 만드니까 메모리 초과를 피할 수 있었다. 

문제를 다 풀고 알게 된 건데 LinkedHahMap을 이용하면 key 값이 입력 순서대로 유지된다는 것을 알았다. 이걸 이용해 다른 문제를 풀어봐야겠다. 비슷한 맥락으로 TreeSet을 사용하면 중복을 제거하면서, 오름차순으로 값을 담을 수 있다. 이걸 그대로 List로 변환한다면 중복이 제거되고 정렬된 상태의 List를 받을 수 있다.

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^