백준 자바 2910 빈도 정렬

이 문제는 빈도라는 단어를 보자마자, 예전에 활용했던 getOrDeafult 함수가 떠올랐다. 따라서, 값들을 먼저 받아서 빈도를 계산한 후
해당 값들을 sort와 compareTo를 활용해서 해결하는 방식으로 구상했다.

package test12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Ox12_Q4_1 {
	// 백준 2910 S3 빈도 정렬
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		// n , c 세팅
		StringTokenizer st= new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		long c = Long.parseLong(st.nextToken());
		
		// n개의 개수 세팅
		Map <String,Integer>cArrMap = new HashMap<>();
		st = new StringTokenizer(br.readLine());
		
		// 입력받은 문자 별 중복 개수 체크
		for(int i = 0; i<n; i++) {
			String temp = st.nextToken();
			cArrMap.put(temp, cArrMap.getOrDefault(temp, 0)+1);
		}
		
		List<String> keySet = new ArrayList<>(cArrMap.keySet());
		
		// Value 값으로 내림차순 정렬
        // 위 comparator 람다 표현식으로
        keySet.sort((o1, o2) -> cArrMap.get(o2).compareTo(cArrMap.get(o1)));
        
        // sb에 hashmap 값들 추가
       	for(String key : keySet) {
    	   int value = cArrMap.get(key);
    	   for(int i = 0; i<value; i++) {
    		   sb.append(key + " ");
    	   }
       }
       System.out.println(sb.toString().trim());
	}
}

먼저 값들을 받아 준 후, 빈도를 계산하기 위한 Hashmap을 생성해준다.
그리고 n개 만큼 반복하여 입력 받음과 동시에 각각의 빈도를 저장한다.
이후 arrayList에 정렬하면서 저장해주고, sb에 추가하여 출력하는 방식이다.

? 틀렸다.

예제는 통과했었으나, 3퍼에서 애매하게 틀렸길래 이건 단단히 글러먹었다고 생각했다.
반례 사례들을 알아보니, 해당 방식으로 구현하다보면 빈도 수가 같은 경우
먼저 입력된 숫자가 먼저 출력되어야하는데 해당 부분에서 오류가 발생한 것이었다.
예를 들면,
6 2
2 1 1 2 1 2
라고 입력하면, 1, 2가 빈도수가 같으므로, 2가 먼저 입력되었으므로,
2 2 2 1 1 1 이 정답인데, 1 1 1 2 2 2 로 출력 아무래도 정렬되는 과정에서
더 작은 수가 앞으로 오게끔 되어있어서 그런 것 같다.

따라서 해당 문제를 해결하기 위해 고안하던 중, HashMap의 형태는 유지하되,
입력된 순서를 기억하는 LinkedHashMap이라는 것을 알게 되었다.

package test12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Ox12_Q4_2 {
	// 백준 2910 S3 빈도 정렬
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		// n , c 세팅
		StringTokenizer st= new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		long c = Long.parseLong(st.nextToken());
		
		// n개의 개수 세팅
		Map <String,Integer>cArrMap = new LinkedHashMap<>();
		st = new StringTokenizer(br.readLine());
		
		// 입력받은 문자 별 중복 개수 체크
		for(int i = 0; i<n; i++) {
			String temp = st.nextToken();
			cArrMap.put(temp, cArrMap.getOrDefault(temp, 0)+1);
		}
		
		List<String> keySet = new ArrayList<>(cArrMap.keySet());
		
		// Value 값으로 내림차순 정렬
        // 위 comparator 람다 표현식으로
        keySet.sort((o1, o2) -> {
        	int precompare = cArrMap.get(o2).compareTo(cArrMap.get(o1));
        	// 만약 value 차이가 같다면, 입력 순서 유지
        	if(precompare == 0) {
        		return 0; // LinkedHashmap 특성, 입력 순서대로 key 유지
        	}
        	return precompare;
        }); // sort fin
        
        // sb에 hashmap 값들 추가
       for(String key : keySet) {
    	   int value = cArrMap.get(key);
    	   for(int i = 0; i<value; i++) {
    		   sb.append(key + " ");
    	   }
       }// for fin
       
       System.out.println(sb.toString().trim());
	}

}

마지막 쯤 정렬하는 구문을 보면, LinkedHashMap을 활용하기도 했지만, 정렬 구문에 대해서도 차이가 있다는 것을 알 수 있다.
value ( 빈도 수 )가 차이가 없다면, return 0을 통해, 입력 순서가 유지 될 수 있도록 하였고, 마지막 출력은 똑같은 방식으로 해결했다.

굿