[백준] 2910 빈도 정렬 [풀이 해설 + 코드]

구현 & 자료구조

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

2910번: 빈도 정렬

 

코드

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
dic = {}

arr = list(map(int, input().split()))

for i in range(len(arr)):
    if arr[i] not in dic:
        dic[arr[i]] = [i, 1, arr[i]]
    else:
        dic[arr[i]][1] += 1 

result = sorted(dic.values(), key=lambda x:(-x[1], x[0]))


ar = []
for i in result:
    for j in range(i[1]):
        ar.append(i[2])
        
print(" ".join(map(str, ar)))

 

설명

해당 문제는 '자료구조를 정확하게 알고 이해할 수 있느냐' 문제라고 생각한다. 구현은 비교적 단순하다. 아이디어 자체를 떠올리는데 크게 어려움이 없었는데 앞서 골드 문제를 풀 때 배웠던 python sorted() 정렬을 할 때 '우선순위'가 중요하다고 이전 문제에서 언급한 바 있었다. 해당 문제가 정확히 그 부분만 보여주고 있다. 우선 이 문제는 '빈도 정렬'이라고 하여 어떠한 수들이 주어졌을 때 그 수가 많이 나온 순서대로 정렬을 하라는 의미다. 하지만 빈도가 많은 순서대로 정렬을 한다면 오답이 되며, 빈도는 많지만 빈도의 수가 똑같을 때를 고려하지 않고 풀이하기 때문이다. 따라서 해당 문제는 빈도가 같을 때를 처리해주어야 하는데 필자는 처음 리스트로 받았을 때의 인덱스 값을 기준으로 딕셔너리에 저장해 주었다 그 이유는 빈도의 수가 같으면 먼저 나온 순서를 출력해야 되기 때문이다. 그렇다면 자료구조 sorted()를 활용하면 쉽게 응용할 수 있다 왜냐하면.

 

 

"빈도는 같은데 index가 빠르면 되니까"

 

 

위와 같은 구문을 생각해본다면 sorted()를 하게 된다면 자연스러워질 수 있다. 왜냐하면 sorted() 함수의 람다 정렬 방식은 매개변수를 앞에서 정한 것을 우선순위를 두고 정렬하되 만약 매개변수가 두 개 이상이라면 두 번째 매개변수를 첫 번째 매개변수가 끝난 뒤에 정렬하기 때문이다. 그렇다면 첫 번째 매개변수는 '빈도를 기준으로 우선 정렬하며 두번째는 index가 빠른 순서대로 정렬하면 빈도가 같을 때 index가 빠른 게 앞에 올 수 있다." 마지막엔 ar에 넣어서 join 하는 방법으로 하여 map()함수로 자료형을 변화해 주고 출력하였다. 사실 이는 더 효율적인 방법이 있으나. python 자료구조 연습을 위해서 여러 가지 방법으로 시도한 풀이 결과다.