347. Top K Frequent Elements ★★★★★

347. Top K Frequent Elements

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count 개수가 k 번째까지 큰거 
        cnt = defaultdict(int)
        for n in nums:
            cnt[n] +=1

        cnt = dict(sorted(cnt.items(), key=lambda x: -x[1]))
        res = []
        for i, (ky, v) in enumerate(cnt.items()):
            res.append(ky)
            if i == k-1:
                return res

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # k 번째까지 큰 빈번수 리턴
        if len(nums) == k:
            return nums

        freq = Counter(nums)
        freq = sorted(freq.items(), key=lambda x: -x[1]) # sorted 이후는 그냥 (num, count) 리스트 임
        
        res = []
        for i, (key, val) in enumerate(freq):            
            if i== k:
                break

            res.append(key)
        return res
            
        # return heapq.nlargest(k, freq.keys(), key=freq.get)

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        if len(nums) == k:
            return nums

        freq = Counter(nums)
        return heapq.nlargest(k, freq.keys(), key=freq.get)

 

---

---

내코드

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 빈번한 숫자중.. k 번째 많이 발생하는 것 까지
        Cnt = Counter(nums)
        # values 로 정렬하면서, 리스트화
        Freq = list(sorted(Cnt.items(), key=lambda x: -x[1]))

        # Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
        # => 뭘 사용하라는 거지?
        res = []
        for i, (ky, v) in enumerate(Freq):
            res.append(ky)
            if i == k-1:
                break
        return res

당신이 작성한 코드는 다음과 같습니다:

Cnt = Counter(nums)  # O(n)
Freq = list(sorted(Cnt.items(), key=lambda x: -x[1]))  # O(n log n)

---

✅ 전체 코드의 시간 복잡도 분석:

1. Counter(nums)
   → 모든 요소를 한 번씩 세므로
   → O(n)
2. sorted(Cnt.items(), key=lambda x: -x[1])
   • Cnt.items()의 길이는 nums에 등장한 **고유 값의 수 = m (m ≤ n)`
   • 이걸 정렬하면
     → O(m log m) ≈ O(n log n) (최악의 경우 모든 값이 다르면 m=n)
3. 결과 추출: for i in range(k):
   → O(k) (k는 최대 n보다 작거나 같음)

---

✅ 최종 시간 복잡도:

O(n log n)

---

❌ 왜 Follow-up 조건에 안 맞나?

• 문제에서 "Your algorithm's time complexity must be better than O(n log n)"라고 명시되어 있어서,
  정렬 기반 접근은 기준을 초과하게 됩니다.
  => O(n log n) 보다 더 적게..!!!

---

✅ 결론:

방식	시간 복잡도	Follow-up 조건 충족 여부
당신의 코드 (정렬)	O(n log n)	❌
Heap 방식	O(n log k)	✅
Bucket Sort 방식	O(n)	✅

✅ [해결 1] Min Heap (O(n log k))

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        # 가장 많이 등장한 k개만 min heap으로 유지
        return [item for item, freq in heapq.nlargest(k, count.items(), key=lambda x: x[1])]

• heapq.nlargest(k, ...)는 내부적으로 min heap을 이용해 O(n log k) 시간에 동작합니다.
• Follow-up 조건 충족!

---

✅ [해결 2] Bucket Sort (O(n))

from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)  # 1. 각 숫자의 빈도 계산
        bucket = [[] for _ in range(len(nums) + 1)]  # 2. 빈도수별 버킷 생성
        """
        nums = [1, 1, 1, 2, 2, 3], len(nums) = 6 이면, 아래와 같이 만들어짐
        bucket = [ [], [], [], [], [], [], [] ]
        # 인덱스:   0   1   2   3   4   5   6
        # 총 길이: 7 (0부터 6까지)
        """

        for num, freq in count.items():  # 3. 숫자를 빈도수에 따라 해당 버킷에 저장
        	"""
            freq를 인덱스로 사용하기 때문에, 리스트지만 사실상 해시맵처럼 사용되는 것
            그리고 이 구조는 정렬이 필요 없고 O(n) 에 동작함
            """
            bucket[freq].append(num)
        """
        이런 의미로 만드는 것임
        bucket =
        [
          [],         # 빈도 0
          [3],        # 빈도 1
          [2],        # 빈도 2
          [1],        # 빈도 3
          [], [], []  # 빈도 4~6
        ]

        """

        res = []
        """
        bucket[빈도]에 해당 숫자들을 저장해서
		뒤에서부터 탐색하면 빈도가 높은 숫자부터 빠르게 꺼낼 수 있음
        """
        for freq in range(len(bucket) - 1, 0, -1):  # 4. 높은 빈도부터 탐색
            for num in bucket[freq]: # bucket[freq] 이 [] 빈 리스트면, 건너띔
                res.append(num)
                if len(res) == k:  # 5. k개를 다 모으면 바로 리턴
                    return res

• 숫자 등장 횟수를 빈도별 버킷에 분류
• 뒤에서부터 탐색 → 높은 빈도부터 수집
• 시간복잡도: O(n)

✅ (중요) for num in bucket[freq]:에서 bucket[freq]가 비어 있으면 자동으로 건너뜁니다.
즉, 아무 일도 하지 않고 그냥 다음 freq로 넘어갑니다.

---

✅ 예를 들어 설명해볼게요:

python

복사편집

bucket = [ [], [], [2], [], [1] ]

여기서 for freq in range(len(bucket)-1, 0, -1): 은
freq = 4 → 3 → 2 → 1 순서로 반복하겠죠?

---

▶ 실행 흐름:

• freq = 4 → bucket[4] = [1] → ✅ 실행됨
• freq = 3 → bucket[3] = [] → ❗비어 있음 → 아무것도 안 하고 다음으로 넘어감
• freq = 2 → bucket[2] = [2] → ✅ 실행됨
• freq = 1 → bucket[1] = [] → ❗비어 있음 → 또 넘어감

---

✅ 결론:

for num in bucket[freq]: 에서 bucket[freq]가 비어 있으면,
파이썬 for 문은 자동으로 아무 것도 반복하지 않고 건너뜁니다.
→ continue 같은 걸 따로 쓸 필요가 없습니다.