문제 설명

메시지를 이루는 숫자들이 주어졌을 때, 이를 빈도 순으로 정렬하는 문제이다.

정렬 기준은 다음과 같다.

1. 더 많이 등장한 숫자가 앞에 온다.
2. 등장 횟수가 같다면 먼저 등장한 숫자가 앞에 온다.

즉, 단순한 숫자 정렬이 아니라

빈도 + 첫 등장 순서

를 함께 고려해야 한다.

---

입력

첫째 줄

N C

• N : 메시지 길이
• C : 숫자의 최대 범위 정보

둘째 줄에는 메시지 수열이 주어진다.

조건

1 ≤ N ≤ 1000
1 ≤ C ≤ 1,000,000,000

여기서 C는 실제 풀이에 거의 쓰이지 않는다.

---

출력

빈도 정렬한 결과를 출력한다.

---

입력 예시

9 77
11 33 11 77 54 11 25 25 33

출력 예시

11 11 11 33 33 25 25 77 54

---

문제 해결 아이디어

이 문제의 핵심은 다음 두 가지이다.

1. 숫자별 등장 횟수
2. 숫자가 처음 등장한 위치

즉 각 숫자마다

• 숫자 값
• 빈도수
• 처음 나온 인덱스

를 관리한 뒤,
이를 기준으로 정렬하면 된다.

---

내가 작성한 코드

나는 먼저 숫자 배열을 정렬한 뒤,
각 숫자의 빈도와 첫 등장 인덱스를 Var 객체에 저장해서 정렬했다.

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int C = sc.nextInt();
        Integer [] num = new Integer[N];
        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < N; i++) {
            num[i] = sc.nextInt();
            if(!map.containsKey(num[i]))    
                map.put(num[i], i);
        }
        
        Arrays.sort(num);
        int tmp = num[0];
        int j = 0;
        Var[] var = new Var[map.size()];
        
        for(int i = 0; i < N; i++) {
            if( i == 0) {
                var[j] = new Var(num[i],map.get(num[i]));
                var[j].upCount();
            }else if( num[i] != tmp) {
                j++;
                var[j] = new Var(num[i],map.get(num[i]));
                var[j].upCount();
                tmp = num[i];
            }else {
                var[j].upCount();
            }
        }
        Arrays.sort(var);
       
        for(Var v : var) {
            v.printNum();
        }
    }
}

class Var implements Comparable<Var>{
    int num;
    int count = 0;
    int index;
    
    public Var(int num, int index) {
        this.num = num;
        this.index = index;
    }
    
    public void upCount() {
        this.count++;
    }
    
    public void printNum() {
        for(int i = 0; i < this.count; i++) {
            System.out.print(num+ " ");
        }
    }

    @Override
    public int compareTo(Var o) {
        if(this.count == o.count)
            return this.index - o.index;
        return  o.count - this.count;
    }
}

---

강의 코드

강의에서는 먼저 숫자와 원래 인덱스를 함께 저장한 뒤,
숫자 기준으로 정렬해서 빈도를 계산했다.

코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Message {
    public Message(int num, int idx) {
        this.num = num;
        this.idx = idx;
    }

    int num;
    int idx;
}

class Frequency {
    public Frequency(int num, int count, int firstIndex) {
        this.num = num;
        this.count = count;
        this.firstIndex = firstIndex;
    }

    int num;
    int count;
    int firstIndex;
}

class Main
{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int C = sc.nextInt();
        Message[] messages = new Message[N];
        for (int i = 0; i < N; i++)
            messages[i] = new Message(sc.nextInt(), i);

        Arrays.sort(messages, new Comparator<Message>() {
            @Override
            public int compare(Message o1, Message o2) {
                return o1.num - o2.num;
            }
        });

        int uniqueCount = 1;
        for (int i = 1; i < N; i++)
            if (messages[i].num != messages[i - 1].num)
                uniqueCount++;

        Frequency[] frequencies = new Frequency[uniqueCount];
        frequencies[0] = new Frequency(messages[0].num, 1, messages[0].idx);
        int frequencyIndex = 0;
        for (int i = 1; i < N; i++) {
            if (messages[i].num != messages[i - 1].num)
                frequencies[++frequencyIndex] = new Frequency(messages[i].num, 0, messages[i].idx);
            frequencies[frequencyIndex].count++;
        }

        Arrays.sort(frequencies, new Comparator<Frequency>() {
            @Override
            public int compare(Frequency o1, Frequency o2) {
                if (o1.count == o2.count)
                    return o1.firstIndex - o2.firstIndex;
                return o2.count - o1.count;
            }
        });

        for (int i = 0; i < uniqueCount; i++)
            while (frequencies[i].count-- > 0)
                System.out.print(frequencies[i].num + " ");
        System.out.println();
    }
}

---

강의 코드 (Map 방식)

강의에서는 LinkedHashMap을 활용한 더 간단한 방식도 제시했다.

코드

import java.util.*;

class Main
{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int C = sc.nextInt();
        Map<Integer, Integer> messages = new LinkedHashMap<>();
        for (int i = 0; i < N; i++) {
            int message = sc.nextInt();
            messages.put(message, messages.getOrDefault(message, 0) + 1);
        }

        Integer[] frequencies = messages.keySet().toArray(new Integer[messages.size()]);
        Arrays.sort(frequencies, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return messages.get(o2) - messages.get(o1);
            }
        });

        for (int frequency : frequencies) {
            int count = messages.get(frequency);
            while (count-- > 0)
                System.out.print(frequency + " ");
        }
        System.out.println();
    }
}

---

내 코드 vs 강의 코드 비교

1. 첫 등장 위치를 처리하는 방식

내 코드

if(!map.containsKey(num[i]))
    map.put(num[i], i);

숫자가 처음 등장한 인덱스를 HashMap에 저장했다.

강의 코드

강의 코드는 Message(num, idx) 객체를 만들어
각 숫자의 원래 위치를 함께 보관했다.

강의 코드(map)

LinkedHashMap을 사용해서
입력 순서를 그대로 유지했다.

---

2. 빈도 계산 방식 차이

내 코드

정렬된 배열을 순회하면서
같은 숫자가 몇 번 나오는지 직접 count

강의 코드

Message 배열을 정렬한 뒤
Frequency 배열로 압축

강의 코드(map)

Map에 넣으면서 바로 빈도 계산

---

3. 핵심 차이

방식	특징
내 코드	정렬 후 직접 그룹핑
강의 코드	객체 분리 후 정렬
강의 코드(map)	LinkedHashMap으로 순서 보존 + 빈도 계산

---

4. 가장 큰 차이점: 순서 보존 방식

이 문제에서 가장 중요한 조건은

빈도가 같으면 먼저 나온 수가 앞에 온다

이다.

내 코드

• HashMap에 첫 등장 인덱스를 저장
• 이후 Var.compareTo()에서 index 비교

강의 코드

• firstIndex를 직접 저장
• 정렬 기준에서 firstIndex 비교

강의 코드(map)

• LinkedHashMap이 입력 순서를 보존
• 그래서 빈도만 비교해도 먼저 나온 것이 자동 유지됨

즉, 이 문제는 단순히 빈도만 세는 문제가 아니라
등장 순서를 어떤 방식으로 보존할 것인지가 핵심이다.

---

핵심 개념

1. 빈도 정렬

이 문제는 일반 정렬이 아니라

빈도 우선 정렬

문제이다.

---

2. 등장 순서 보존

동일 빈도일 때는 숫자의 크기가 아니라

처음 나온 순서

를 기준으로 해야 한다.

---

3. LinkedHashMap

강의의 map 풀이에서 가장 중요한 자료구조는

LinkedHashMap

이다.

이 자료구조는

• HashMap처럼 key-value 저장 가능
• 입력 순서를 유지

한다.

그래서 이 문제처럼 “먼저 등장한 순서”가 중요할 때 매우 유용하다.

---

4. 커스텀 정렬

이 문제에서도 Comparator 또는 Comparable을 사용해
정렬 기준을 직접 정의해야 한다.

예를 들어 내 코드의 핵심 비교 기준은 다음과 같다.

if(this.count == o.count)
    return this.index - o.index;
return o.count - this.count;

의미는

1. 빈도가 다르면 빈도 내림차순
2. 빈도가 같으면 첫 등장 인덱스 오름차순

이다.

---

시간 복잡도

내 코드

• 숫자 정렬: O(N log N)
• 그룹핑: O(N)
• Var 정렬: O(M log M) (M = 서로 다른 숫자 개수)

전체적으로

O(N log N)

---

강의 코드

비슷하게

O(N log N)

이다.

---

강의 코드(map)

• 빈도 계산: O(N)
• key 정렬: O(M log M)

전체적으로도 충분히 빠르다.

---

정리

이 문제는 단순한 정렬 문제가 아니라

빈도 + 첫 등장 순서

를 함께 다루는 문제였다.

내 코드는

• 배열 정렬
• 첫 등장 인덱스 저장
• 사용자 정의 클래스 정렬

방식으로 해결했다.

강의 코드는

• 객체 배열을 사용한 정렬 방식
• LinkedHashMap을 활용한 더 간단한 방식

두 가지를 보여주었다.

핵심 차이는 다음과 같다.

내 코드   → 첫 등장 인덱스를 따로 저장
강의 코드 → firstIndex 또는 LinkedHashMap으로 순서 보존

이 문제를 통해 정리할 수 있는 중요한 포인트는 다음과 같다.

1. 빈도 정렬은 단순 숫자 정렬과 다르다
2. 동일 빈도일 때의 기준을 반드시 확인해야 한다
3. LinkedHashMap은 입력 순서 보존이 필요한 문제에서 강력하다
4. Comparator / Comparable을 이용해 문제 조건에 맞는 정렬 기준을 직접 정의할 수 있어야 한다