백준_python 2910번 빈도 정렬 (해시, 정렬, lambda)

<문제 링크>

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

 

주어진 수열을 빈도, 출현순서 순으로 정렬하여 출력

 

<정답 코드>

 sol 1) 딕셔너리에 저장 후 람다식으로 정렬 (72ms)

from collections import defaultdict
 
n, c = map(int, input().split())
nums = list(map(int, input().split()))
 
dic = defaultdict(int)
for i in nums:
    dic[i] += 1
 
sorted_dic = sorted(dic.items(), key = lambda x: (-x[1], list(dic.keys()).index(x[0])))
 
for i, j in sorted_dic:
    for _ in range(j):
        print(i, end=' ')

 

 

 

 sol 2) 딕셔너리에 저장 후 람다식으로 정렬 - 시간복잡도 개선 (36ms)

n, c = map(int, input().split())
nums = list(map(int, input().split()))
 
dic = {}
order = 0
 
# dic[숫자] = [빈도, 출현순서] 형태로 저장
for i in nums:
    if i in dic:
        dic[i][0] += 1
    else:
        dic[i] = [1, order]
        order += 1
# 출현빈도(내림차순), 출현순서(오름차순) 순으로 정렬
sorted_dic = sorted(dic.items(), key = lambda x: (-x[1][0], x[1][1]))
 
result = []
# 출현횟수만큼 result에 추가(append 반복보다 빠름)
for num, (cnt, _) in sorted_dic:
    result.extend([num] * cnt)
 
# * : 리스트 요소 개별 인자로 출력
print(*result)

 

sol 1에 비해 소요시간이 절반 수준으로 감소

이유 : sol 2 line 15에서 정렬 시 매번 리스트 생성하는 반복(sol1 line 10)을 제거 

 

 

 

 

 

식을 복잡하게 만드는 것 보다 필요한 정보를 저장해두고 꺼내 쓰는 것이 편리

람다식 연습하기

리스트 출력 시 * 사용하면 편리