[자바] 백준 2910 - 빈도 정렬 (java)

 문제 : boj2910

---

 

필요 알고리즘 개념

• 해시를 사용한 집합과 맵
  
  • N은 1000인데 C가 10억이나 된다. 해시를 사용하지 않을꺼라면 값 압축을 해야하는데 그게 더 귀찮으므로 해시를 사용하는게 편하다. 자바로 따지면 HashMap이 필요하다.
• 정렬
  
  • 커스텀 정렬이 필요한 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  정렬 및 출력에 필요한 정보는 3가지이다.

1. 숫자

2. 해당 숫자가 처음 나온 위치 번호

3. 해당 숫자가 나온 횟수

 

  그렇다면 위 정보 3가지로 우선 class를 만들자. 내 경우엔 Msg 라고 만들었다. 그리고 차례대로 num, idx, cnt가 위의 정보를 나타낸다.

 

  num, idx, cnt 정보를 가진 객체들만 정상적으로 만들 수 있다면 커스텀 정렬을 통해 이 문제를 풀 수 있다. 내 경우엔 다음의 로직으로 풀었다.

A. 만약 입력으로 들어온 수가 HashMap에 존재하지 않을 경우, 해당 num이 처음 나온 것이므로 위치를 알 수 있다. 따라서 HashMap에 num, idx, cnt=1 객체를 만들어 넣어준다. 이 때 차후 정렬을 해야하므로 ArrayList도 하나 만들고, 방금 HashMap에 넣었던 객체를 마찬가지로 넣어준다.

 

B. 만약 입력으로 들어온 수가 HashMap에 존재한다면 (이미 존재하는 key값이라면), 해당 객체의 cnt를 1 증가시켜준다.(inc 함수)

 

 C. ArrayList에는 이제 모든 정보를 포함하는 객체들이 존재한다. num은 출력에 필요한거니 idx와 cnt를 기준으로 정렬을 해준다. SQL로 따지면 ORDER BY cnt DESC, idx ASC 로 정렬해주면 된다. (compareTo 함수 참고)

 

D. 이제 정렬된 ArrayList에서 하나씩 꺼내면서, 해당 객체의 num을 해당 객체의 cnt번씩 출력해주면 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

class Msg implements Comparable<Msg> {
    int num, idx, cnt;
    public Msg (int num, int idx ,int cnt) {
        this.num = num;
        this.idx = idx;
        this.cnt = cnt;
    }
    public void inc() { this.cnt++; }

    @Override
    public int compareTo(Msg o) {
        if (this.cnt == o.cnt)
            return this.idx - o.idx;
        return o.cnt - this.cnt;
    }
}

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        HashMap<Integer, Msg> hm = new HashMap<>();
        ArrayList<Msg> list = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int cur = Integer.parseInt(st.nextToken());
            if (!hm.containsKey(cur)) {
                Msg tmp = new Msg(cur, i, 0);
                hm.put(cur, tmp);
                list.add(tmp);
            }
            hm.get(cur).inc();
        }
        Collections.sort(list);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            Msg tmp = list.get(i);
            int num = tmp.num;
            int cnt = tmp.cnt;
            while (cnt-->0)
                sb.append(num).append(' ');
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}