Leetcode #347 Top K Frequent Elements

문제

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):

    numdict = {}
    result = []
    for x,y in enumerate(nums):
       numdict[y] = 0
   
    for i in nums:
       numdict[i] = nums.count(i)
    
    result = sorted(numdict.items(),reverse=True, key = lambda x : x[1])
    
    return list(dict(result).keys())[0:k]

• elements의 갯수를 셀 딕셔너리 선언

• 딕셔너리의 key를 value 기준으로 정렬할 result 선언

• nums를 딕셔너리로 만든 후 for loop로 elements count

• for문이 끝난 딕셔너리를 sorted 함수를 이용하여 value값 기준으로 정렬
  1) items() 함수를 이용해 value값만 빼서
  2) reverse=True를 이용해 default인 오름차순이 아닌 내림차순으로 정렬하고
  3) key= lambda x : x[1]을 이용해 [(key , value), ...]의 튜플형태로 반환

• 반환하려는 값은 자주 등장하는 숫자의 갯수가 아닌 숫자이므로 keys() 메서드를 이용해 딕셔너리화 한 뒤 리스트로 만들어 k값만큼 리스트 슬라이싱

Collections

collections - 컨테이너 데이터형

더 좋은 풀이가 없나 검색해보다가 파이썬에서 라이브러리로 제공하는 collections 모듈을 알게 되었다.

collections에는 데이터 처리를 위한 유용한 객체가 많은데, 그 중 counter()는 리스트를 해싱해서 갯수를 세는데 유용하다.

여기서 counter()의 most_common(n) 메서드는 지정한 배열의 원소를 내림차순으로 정렬하고, n만큼 (element, count)의 튜플형태로 반환한다.

이를 이용하면 획기적으로 코드를 간결하게 만들 수 있다.

from collections import Counter

def top_k(nums, k):

    result = Counter(nums).most_common(k)
    answer = [num[0] for num in result]
    return answer

• 파라미터로 들어온 nums를 k만큼 내림차순의 튜플형태로 반환
  [(nums[x], nums.count(x) , (nums[y], nums.count(y)) ... ]

• 리스트 컴프리헨션을 사용해 result의 튜플의 첫번째 원소인 key(nums[x],nums[y]..)만 빼서 리스트로 변환후 반환

시간의 여유가 된다면 collections 모듈에 대해 더 살펴봐야겠다.