[99클럽 코테 스터디] 21일차 TIL - 정렬, Top K Frequent Elements

[21일차] 정렬

문제: https://leetcode.com/problems/top-k-frequent-elements/description/

* 번역: 정수 배열 nums와 정수 k가 주어질 때, 가장 자주 등장하는 원소들 k개를 반환하라. 반환할 답은 순서대로여야 한다. 

My Solution

배열을 순회하며 등장 횟수를 세고, 가장 많이 등장한 k개 원소를 출력하는 방식을 그대로 코드에 적용했다.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        ans = []
        key = set(nums)
        dic = {i: 0 for i in key}

        for i in nums:
            dic[i] += 1

        # value값을 기준으로 내림차순 정렬
        sorted_items = sorted(dic.items(), key=lambda x: x[1], reverse=True)

        # 빈출 원소 저장
        for i in range(k):
            ans.append(sorted_items[i][0])

        return ans

코드 흐름 및 내용은 다음과 같다.

주어진 nums 배열이 어떤 정수를 포함하고 있는지, set 메서드를 통해 중복을 제거한 집합 자료형을 만들어 key값으로 쓸 리스트를 만든다.

key = set(nums)
dic = {i: 0 for i in key}

이 과정을 거치면 dic = {1: 0, 2: 0, 4:0} 와 같이 value는 0으로 초기화 된 사전형 변수를 얻게 된다. 

가장 많이 등장한 원소를 반환해야 하므로, 등장 횟수를 의미하는 value를 기준으로 정렬을 수행해주어야 한다.

사전 자료형은 sort 메서드가 없고, 사전의 요소들을 튜플 형태로 바꾸어서 리스트 자료형에 저장해주면 sort 메서드를 사용할 수 있게 된다.

# value값을 기준으로 정렬
sorted_items = sorted(dic.items(), key=lambda x: x[1], reverse=True)

sorted_items 는 [(1, 3), (2, 2), (3, 1)] 와 같은 형태로, (숫자, 등장횟수)를 의미하는 튜플을 원소로 가지고, 등장 횟수를 기준으로 내림차순으로 저장된다. 

# 빈출 원소 저장
for i in range(k):
    ans.append(sorted_items[i][0])

return ans

튜플은 인덱싱이 가능하므로, 튜플의 첫 원소[i][0] 를 답으로 출력한다. 

위의 코드는 반복문 외에도 한 줄로 아래와 같이 쓸 수 있다.

return [x for x,y in sorted_items[0:k]]

답에 적지 않은 이유는 Runtime이 반복문을 사용했을 때보다 적지 않은 것 같아서 🤔

Another Solution

collections모듈의 Counter 클래스에서 most_common() 메서드를 활용할 수 있다.

이 메서드는 데이터의 개수를 셀 때 유용한 클래스로, key-value 형태의 데이터를 다루는 해시(hash)문제에서 유용하게 사용된다.

from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return list(map(lambda x:x[0], Counter(nums).most_common(k)))

Counter 클래스의 most_common 메서드는 정말 이 문제를 위해 만들어졌다고 할 정도로 딱 이 기능을 수행하는 메서드다.

map함수는 Counter(nums).most_common(k)의 결과로 반환되는 리스트 [(1, 3), (2, 1)] 에서 튜플의 첫 원소만을 반환하기 위해 사용했다.

나다어

나는 다음에 어떻게 풀까

• lambda는 이름 없는 (한 줄의) 함수를 의미하고, lambda 매개변수: 표현식 으로 정의할 수 있다.
• map함수는 리스트(반복 가능한 객체)의 모든 원소에 원하는 동작을 수행시킬 수 있다.
• collections 모듈의 Counter 클래스는 데이터의 갯수를 세는 데 사용된다.
• 딕셔너리형은 sort() 메서드가 적용 안된다.
• 리스트 중복 제거는 dict()가 아닌 set()

lst = [1, 1, 1, 2, 2, 3]
unique_lst = list(set(lst))
print(unique_lst)

https://velog.io/@eunhye_/python-collections-Counter

파이썬 collections 모듈의 Counter 사용하기