[코테] 99클럽 코테 스터디 32일차 TIL - 정렬

Question1 - [미들러] Top K 최빈값 찾기 (Top K Frequent Elements)

 

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

 

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

 

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Example 2:

Input: nums = [1], k = 1

Output: [1]

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

---

 

문제풀이

주어진 리스트에 대해, K번째까지의 최빈값을 반환하는 문제. 담기는 순서는 상관 없다.

 

trial1 - Counter 사용 

 

Counter는 요소들을 빈도값 순으로 계산하여 반환하는 기능이다.

Counter 실행 결과는 아래 예시와 같음. 아래처럼 딕셔너리 형태로 요소별 개수가 반환된다.

nums = [1,1,1,2,2,3,3,3,3,3,3,3]
counter = Counter(nums)
counter

# 실행 결과 
Counter({1: 3, 2: 2, 3: 7})

 

이렇게 만든 counter 객체에서, 요소를 개수가 많은순으로 정렬하기 위해 람다 함수를 사용해줄 수 있다.

이렇게 나온 결과에서 K번째 값까지를 반환하면 될 것이다.

ranking = sorted(counter, key=lambda x : counter[x],reverse=True)
ranking

# 실행 결과
[3, 1, 2]

 

풀이는 아래와 같다.

• counter 객체를 생성  : nums의 요소가 개수별로 count됨
• ranking 변수에 많은 순으로 정렬한 리스트를 담음 
• ranking 에서 k번째 요소까지만 result 리스트에 담음
• result 반환 

from collections import Counter

class Solution(object):
    def topKFrequent(self, nums, k):
        count = Counter(nums)
        
        ranking = sorted(count, key=lambda x: count[x], reverse=True)
        result = []
        for i in range(k):
            result.append(ranking[i])
        
        return result

 

---

trial2 - Counter의 most_common 메소드 사용 

 

Counter의 most_common이라는 메소드를 사용해줄 수도 있다.이 메소드는 튜플로 많은 개수 순으로 (요소, 개수) 를 아래와 같이 반환한다.

nums = [1,1,1,2,2,3,3,3,3,3,3,3]
counter = Counter(nums)

counter.most_common()

# 실행 결과
[(3, 7), (1, 3), (2, 2)]

 

k 파라미터로 Top K까지를 반환할 수도 있다. 

counter.most_common(2)

# 실행 결과 
[(3, 7), (1, 3)]

 

이 경우에 실행 결과의 첫번째 인덱스 (요소값)만 아래와 같이 반환하면 된다.

• counter 객체를 생성  : nums의 요소가 개수별로 count됨
• ranking 변수에 most_common의 k번째까지 값을 담기 
• ranking에서 튜플의 첫번째 요소만 result 리스트에 담음
• result 반환 

from collections import Counter

class Solution(object):
    def topKFrequent(self, nums, k):
        count = Counter(nums)
        
        ranking = count.most_common(k)
        
        result = [item[0] for item in ranking]
        
        return result