문제 개요
어떤 배열에는 동일한 요소가 여러 번 나타날 수 있습니다. 이때 배열을 각 요소의 등장 빈도가 증가하는 순서로 정렬하려고 합니다. 즉, 덜 자주 나타나는 요소일수록 앞쪽에 배치되고, 빈도가 같은 요소들 사이에서는 값이 큰 요소가 먼저 오도록 정렬하는 것입니다.
예를 들어 입력이 다음과 같다면,
nums = [1,5,3,1,3,1,2,5]
출력은 아래와 같습니다.
[2, 5, 5, 3, 3, 1, 1, 1]
그 이유를 살펴보면 다음과 같습니다.
- 2는 1번 등장
- 5와 3은 각각 2번 등장 (같은 빈도일 때는 값이 큰 5가 먼저)
- 1은 3번 등장
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
mp := 새로운 딕셔너리(맵)를 생성합니다.
nums의 각 고유 요소 i에 대해 다음을 수행합니다.
x := nums에서 i가 나타난 횟수
x가 mp에 이미 존재하면, mp[x] 리스트의 끝에 i를 추가합니다.
그렇지 않으면, mp[x] := i 하나만 담긴 새로운 리스트로 설정합니다.
ans := 결과를 저장할 새로운 리스트를 생성합니다.
키를 기준으로 정렬된 mp의 각 i에 대해 다음을 수행합니다.
mp[i]를 내림차순으로 정렬한 리스트의 각 j에 대해, j를 i번 반복하여 ans에 추가합니다.
ans를 반환합니다.
파이썬 구현 예제
아래 구현을 통해 더 잘 이해할 수 있습니다.
def solve(nums):
mp = {}
for i in set(nums):
x=nums.count(i)
try:
mp[x].append(i)
except:
mp[x]=[i]
ans=[]
for i in sorted(mp):
for j in sorted(mp[i], reverse=True):
ans.extend([j]*i)
return ans
nums = [1,5,3,1,3,1,2,5]
print(solve(nums))입력
[1,5,3,1,3,1,2,5]
출력
[2, 5, 5, 3, 3, 1, 1, 1]
동작 원리 설명
이 코드의 핵심 로직은 다음과 같습니다.
- 빈도 계산: set(nums)로 중복을 제거한 후, count() 메서드로 각 요소의 등장 횟수를 구합니다.
- 빈도별 그룹화: 딕셔너리 mp의 키를 '빈도', 값을 '해당 빈도를 가진 요소들의 리스트'로 사용하여 요소들을 그룹화합니다.
- 정렬 및 재구성: 빈도(키)를 오름차순으로 순회하면서, 같은 빈도 내에서는 요소를 내림차순 정렬한 뒤 해당 빈도만큼 반복해 결과 리스트에 추가합니다.
참고로 파이썬에서는 collections.Counter와 sorted 함수의 key 매개변수를 활용하면 더 간결하게 구현할 수도 있습니다.
from collections import Counter
def solve(nums):
cnt = Counter(nums)
return sorted(nums, key=lambda x: (cnt[x], -x))두 방법 모두 시간 복잡도는 O(n log n)으로 동일하지만, Counter를 사용하는 방식이 코드가 더 짧고 가독성이 좋습니다.