문제
nums는 숫자로 이루어진 배열입니다.
가장 자주 등장한 숫자를 k 개수만큼 return해주세요.
nums = [1,1,1,2,2,3],
k = 2
return [1,2]
nums = [1]
k = 1
return [1]내코드
def top_k(nums, k):
num_count = {}
result = []
for i in nums:
if i in num_count:
num_count[i] += 1
else:
num_count[i] = 1
num_count = sorted(num_count.items(), key=lambda x: x[1], reverse=True)
for i in range(k):
result.append(num_count[i][0])
return result나는 nums의 숫자를 count해서 dictionary형식으로 정리했다(key=숫자, value=count). 이 dictionary는 collections.Counter함수를 쓰면 바로 만들 수 있다. 하지만 여기서는 사용하지 않았다.
dictionary session에서 배웠듯이, 딕셔너리는 key의 해쉬값으로 정렬되기 때문에 unsorted된 상태이다. 이 문제에서는 가장 많은 빈도가 나온 숫자를 k개만큼 가지고와야므로 value가 큰 순서순으로 딕셔너리를 정렬해주려고 한다.
그렇게하기 위해서는 sorted함수가 필요하다. sorted함수의 key 파라메터는 각 값들을 비교하기 전에 각 요소에서 호출되어야하는 함수를 지정하는 것이다. 즉, key파라메터에 들어간 함수(value만 가져오기)가 각 item(튜플)에 적용되어 value값끼리 비교가 되고 정렬이 되는 것이다. value가 큰 값부터 정렬해야하므로 reverse=True로 설정해준다.
이렇게 정렬된 딕셔너리를 k만큼 돌려서 key를 list에 담으면 빈도수가 많은 숫자들을 k개만큼 선택할 수 있다.
Model Solution
def top_k(nums, k):
count = {}
for n in nums:
count[n] = count.get(n, 0) + 1
bucket = [[] for _ in range(len(nums)+1)]
for n, freq in count.items():
bucket[freq].append(n)
ret = []
for n_list in bucket[::-1]:
if n_list:
ret.extend(n_list)
if len(ret) == k:
return ret내가 딕셔너리를 만들때 썼던 for문을 여기서는 2줄로 간단하게 나타냈다.👍
그리고 빈 리스트가 nums의 갯수만큼 들어간 bucket list를 만들어준다. count 딕셔너리의 key를 n, value를 freq로 설정하고 freq를 index로해서 bucket에 n을 넣어준다.
이게 그냥 말로만 하면 이해가 잘 안될수도 있는데 만약 nums=[1,1,2]였다면 처음에는bucket = [[], [], [], []] 이렇게 bucket이 생성되고 freq에 맞춰서 n을 넣으면 bucket = [[], [2], [1], []]이 된다.
freq가 높은 순서대로 나와야하므로 bucket을 역으로 정렬하고, 들어있는 숫자를 하나씩 ret리스트에 추가해준다. 하지만 bucket에 빈 list도 존재하기 때문에 추가해준 후에 ret의 길이가 k만큼이 되면 그때 ret을 return한다.
