[1스4코2파] # 173. LeetCode 347. Top K Frequent Elements (Array&Hashing)

gunny·2023년 6월 25일

1스4코2파 LeetCode 347 LeetCode 347 python LeetCode Array & Hashing LeetCode Top K Frequent Elements Leetcode Top K Frequent Elements python leetcode

코딩테스트

목록 보기

174/530

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (173차)
[4코1파] 2023.01.13~ (165일차)
[1스4코1파] 2023.04.12~ (76일차)
[1스4코2파] 2023.05.03 ~ (54일차)

Today :

2023.06.25 [173일차]
LeetCode Patterns
https://leetcode.com/problems/top-k-frequent-elements/description/

347. Top K Frequent Elements

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

문제 설명

int형 datatype의 원소로 구성된 list가 주어질 때,
list 내의 원소의 frequency 빈도가 있으면
같이 주어지는 k개의 개수만큼 해당 원소를 리스트로 반환해라

문제 풀이 방법

그냥 collection에 있는 Counter로 주어진 리스트에 있는 원소들을 센 값을 hashing.. dictionary로 만듦
key는 element, values는 list에 있는 element의 개수 인 것임..
다음에 sorted reverse.. values를 내림차순으로 정렬한담에 주어진 k만큼만 인덱스로 key 뽑아오면 됨

내 코드

처음 그냥 푼 코드

from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        numDict = dict(Counter(nums))
        return [i for i,j in sorted(numDict.items(), reverse=True, key=lambda x: x[1])[:k]]

O(nlogn) 영상보고 가져온 코드

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = {}
        freq = [[] for _ in range(len(nums)+1)]
        ans = []

        for num in nums:
            cnt[num] = 1+cnt.get(num,0)
        for key,val in cnt.items():
            freq[val].append(key)

        for i in range(len(freq)-1, 0, -1):
            for j in freq[i]:
                ans.append(j)
                if len(ans)==k:
                    return ans

증빙

내꼬