[JAVA] BOJ_2910. 빈도 정렬

🦍 문제

2910번: 빈도 정렬

 

---

🐈 문제 풀이 

1. 무엇을 구해야 할까?

주어진 숫자들의 빈도를 계산한 후, 빈도수가 높은 숫자들부터 순서대로 출력한다.

빈도수가 같다면 먼저 나왔던 숫자들을 우선적으로 출력한다.

 

2. 어떻게 구해야 할까?

1) 빈도수를 구해야 한다.

 - 보통 빈도수를 구하는 방법으로는 배열을 사용하는 방법을 떠올릴 수 있지만 입력되는 수의 최댓값이 10억이기에  HashMap 자료구조를 이용하였다.

 - key 값으로는 입력받은 숫자를, value로는 빈도수를 저장하였다.

 - HashMap에 저장된 값을 빈도수(value) 순으로 정렬하기 위해 배열과 Arrays.sort 메서드도 함께 이용하였다.

 

2) 빈도수가 같다면, 먼저 나왔던 숫자들을 우선적으로 출력해야 한다.

 - 숫자들을 입력받는 순서를 기억해야 한다. 따라서 컬렉션에 값이 입력되는 순서대로 저장되는 LinkedHashMap 자료구조를 이용하였다.

 

3. 특별히 고려해야 할 사항은?

 - 위에서 모두 설명되었듯이 입력되는 수의 크기에 유의하며, 숫자가 입력되는 순서들을 유지해야 한다는 부분을 해결하기 위해 적절한 자료구조의 선택을 고려하면 좋을 것 같다.

 

---

🐕‍🦺 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.StringTokenizer;

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

		// N, C 입력
		int N = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());

		// 입력된 순서를 보장받는 LinkedHashMap 선언
		Map<Integer, Integer> map = new LinkedHashMap<>();

		// N개의 수를 해시맵에 저장
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; ++i) {
			int n = Integer.parseInt(st.nextToken());
            
			// map : [입력받은 값 : 빈도수]
            map.put(n, map.getOrDefault(n, 0) + 1);
		}

		// arr : [0] = 입력받은 수, [1] = 빈도수
		int[][] arr = new int[N][2];

		// itr : 해시맵의 key값들을 순차적으로 순회할 iterator
		Iterator itr = map.keySet().iterator();

		for (int i = 0; itr.hasNext(); ++i) {
			int key = (Integer) itr.next();
            
            // arr[i][0] : 입력 받은 값, arr[i][1] = 빈도수
			arr[i][0] = key;
			arr[i][1] = map.get(key);
		}

		// 빈도수 순으로 정렬
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o2[1] - o1[1];
			}
		});
        
        // 빈도수 순으로 정렬된 arr을 순회
		for (int[] i : arr) {
        
        	// 해당 값의 빈도수 만큼 반복해서 출력
			while (i[1]-- > 0) {
				sb.append(i[0]).append(" ");
			}
            
            // 더 이상 값이 존재하지 않다면 for문 종료
			if (i[0] == 0 && i[1] == 0) {
				break;
			}
		}
		
        // 정답 출력
		System.out.println(sb);
	}
}

---

 

---

🐖 Think

- 기본기를 다지기 위해 자료구조 문제들을 위주로 풀이하고 있다. 문제의 조건을 살펴 적절한 자료구조를 선택하는 능력을 기를 수 있었다.