2910 - 빈도 정렬

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

 

1. 메인 아이디어

  - 각 원소에 대해 [빈도, 순번]을 정렬할 자료구조를 생각한다 -> dictionary가 적합

  - dictionary를 key=lambda(=익명함수)를 기준으로 정렬한다

    > -x[1][0] = 각 원소의 빈도를 우선으로 내림차순

    > x[1][1] = 각 원소의 순번을 그 다음으로 오름차순

  - result에 정렬된 dictionary를 원소 * 빈도로 extend한다 ( dictionary 내부 원소는 list 이므로 extend 써야함)

    > result = [], extend ([2,3], [1,2] ..) => result = [2, 2, 2, 1, 1]

 

2. 소스 코드

# 백준 2910 빈도 정렬
# 수열은 N개로 이루어져 있고 숫자는 모두 C보다 작거나 같다
# 수열 내에 두 수 X와 Y가 있을 때 X가 더 앞에 있어야 함
# 메시지의 길이 N과 C가 주어진다 

# 5 2
# 2 1 2 1 2
import sys
input = sys.stdin.readline

# 입력 받기
n, c = map(int, input().split())
seq = list(map(int, input().split()))

# 빈도와 첫 번째 인덱스를 저장할 딕셔너리
count = {}
for idx, num in enumerate(seq):
    if num in count:
        count[num][0] += 1  # 빈도 증가
    else:
        count[num] = [1, idx]  # 빈도와 첫 등장 인덱스 저장

# 빈도와 인덱스를 기반으로 정렬
sorted_numbers = sorted(count.items(), key=lambda x: (-x[1][0], x[1][1])) # -x[1][0] 은 빈도를 기준으로 내림차순, x[1][1] 순서를 기준으로 오름차순
# x[1]은 count[num] -> ex:) [3, 0]
# x[1][0]은 특정 숫자의 빈도를 의미

# 결과 리스트 생성
result = []
for num, (freq, _) in sorted_numbers:
    result.extend([num] * freq)  # 각 숫자를 빈도만큼 추가

# 결과 출력
print(*result)