[백준] 2910 빈도 정렬 - LinkedHashMap(링크드해시맵) + LinkedHashSet(링크드해시셋) + Comparable JAVA

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

2910번: 빈도 정렬

코드설명

LinkedHashMap + Comparable 을 활용합니다.

 

문제에서 가장 중요한 조건은, "만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다." 라는 조건입니다.

 

문제에서 HashMap을 사용하지 않는다면,

1. ArrayList를 순회하면서 찾기

2. int[1,000,000,000] arr 만큼의 배열을 만들어놓고 해당 배열에 값 들어올떄마다 1씩 증가시키기.

 

이렇게 2가지 방식이 있습니다.

ArrayList를 활용할경우에는 매번 삽입시마다 해당하는 숫자를 찾아야하기에 O(N*N) 시간복잡도가 걸립니다.

int[1000000000] arr을 활용할경우에는 먼저 나온 것이 앞에 있어야한다는 조건을 만족시키기 위해 따로 해당 숫자의 가장 첫번쨰 위치를 저장시켜야하는 ArrayList를 만들어서 관리해야합니다. 그렇게 되면 로직 복잡성이 증가합니다.

 

그대신에 LinkedHashMap을 활용하여 들어온 순서를 보장한다면, 별도의 로직없이 처리가 가능합니다

 

 

두번쨰 풀이는, LinkedHashSet과 LinkedHashMap을 활용합니다.

먼저, 시간복잡도의 경우 HashSet에 존재하는 메세지의 종류가 최대 N개, 그리고 이 N개를 1000번 순회하므로 시간복잡도는 10^6 입니다.

코드

package algorhythm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map.Entry;
import java.util.StringTokenizer;

public class Main {
	public static int N, C;
	static HashMap<Integer, Integer> hashmap = new LinkedHashMap<Integer, Integer>();
	static ArrayList<Node> arr = new ArrayList<Node>();
	static ArrayList<Node> firstIndexArr = new ArrayList<Node>();
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			int a = Integer.parseInt(st.nextToken());
			hashmap.put(a, hashmap.getOrDefault(a, 0) + 1);
			
		}
		
		for(Entry<Integer, Integer> entrySet : hashmap.entrySet()) {
			arr.add(new Node(entrySet.getKey(), entrySet.getValue()));
		}
		
		Collections.sort(arr);

		StringBuilder sb = new StringBuilder();
		for(Node temp : arr) {
			for(int i=0;i<temp.cnt;i++) {
				sb.append(temp.num).append(" ");
			}
		}
		System.out.println(sb.toString());
	}
}
class Node implements Comparable<Node>{
	int num;
	int cnt;
	public Node(int num, int cnt) {
		this.num = num;
		this.cnt = cnt;
	}
	@Override
	public int compareTo(Node other) {
		if(this.cnt < other.cnt) {
			return 1;
		} else if(this.cnt == other.cnt){
			return 0;
		} else {
			return -1;
		}
		
	}
}

 

LinkedHashSet과 LinkedHashMap을 활용합니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;

public class Main {
    public static int N, M, C;
    public static int answer = 0;
    public static int[] arr;
    public static LinkedHashSet<Integer> hashset = new LinkedHashSet<>();
    public static LinkedHashMap<Integer, Integer> hashmap = new LinkedHashMap<>();
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			hashset.add(arr[i]);
			hashmap.put(arr[i], hashmap.getOrDefault(arr[i], 0) + 1);
		}
		
		int kind = hashset.size();
		int mostFrequencyValue = -1;
		int mostFrequencyKey = -1;
		for(int i=0;i<kind;i++) {
			mostFrequencyValue = -1;
			mostFrequencyKey = -1;
			for(int v : hashset) {
				if(mostFrequencyValue < hashmap.get(v)) {
					mostFrequencyValue = Math.max(mostFrequencyValue, hashmap.get(v));
					mostFrequencyKey = v;
				}
			}
			for(int j=0;j<mostFrequencyValue; j++) {
				sb.append(mostFrequencyKey).append(" ");
			}
			hashmap.remove(mostFrequencyKey);
			hashset.remove(mostFrequencyKey);
		}
		System.out.println(sb);
	}
    

}