p. 307: 31. 상위 K 빈도 요소 - 최적화 & 파이써닉한 코드 질문

[nayeonshin]

안녕하세요,

307쪽 31번 문제(상위 K 빈도 요소)에서 힙과 Counter() 객체를 활용한 풀이 2개에 대해 질문 몇 개를 여쭤보고자 합니다.

질문 1 - O(n log n) 시간 복잡도 풀이를 O(n log k)로 최적화하는 것이 의미가 있을까요?
책에 수록된, 최대힙을 활용한 풀이

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqs = collections.Counter(nums)  # O(n) 시간 & O(n) 공간 (여기서 `n`은 len(nums))
        freqs_heap = []
        for f in freqs:
            heapq.heappush(freqs_heap, (-freqs[f], f))  # `freq_heap`: O(n log n) 시간 & O(n) 공간

        topk = list()
        for _ in range(k):
            # 아웃풋 리스트인 `topk`를 공간 복잡도 계산에 고려하지 않았을 때, O(k log n) 시간 & O(1) 공간
            topk.append(heapq.heappop(freqs_heap)[1])

        return topk

이 풀이에서 Counter() 객체의 값을 음수화하여 (-freqs[f]) 힙에 삽입함으로써 최대힙을 구현하는데, n이 len(nums)라면, 이 풀이의 경우 시간 복잡도가 O(n log n), 공간 복잡도가 O(n)인 것을 볼 수 있습니다.

사소한 최적화이지만 최소힙을 활용하면 시간 복잡도를 O(n log k)로 줄일 수 있을 것 같은데, 이러한 최적화가 의미가 있을까요? "의미있음"은 주관적인 개념이긴 하지만, "면접 상황에서 이러한 최적화가 도움이 될까" 정도로 보시면 될 것 같습니다.

# 제 풀이
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    # ⭐ 최적화 방법 1: n == k일 경우 바로 `nums`를 리턴함으로써 k < n을 보장 (여기서 `n`은 len(nums))
    if len(nums) == k:
        return nums

    min_heap = []  # ⭐ 최적화 방법 2: 최대힙 대신 최소힙 사용하기
    nums_to_counts = Counter(nums)  # O(n) 시간 & O(n) 공간

    for num, count in nums_to_counts.items():  # O(n log k) 시간 & O(k) 공간
        heappush(min_heap, (count, num))

        # 최소힙의 길이(혹은 사이즈)가 `k`를 넘어가면, 루트(최솟값)를 pop하면서 마지막에 상위 K 빈도 요소만 남겨둠
        # min_heap의 공간 복잡도는 O(k)지만 위 Counter() 객체 때문에 풀이의 공간 복잡도는 결론적으로 O(n)
        if len(min_heap) > k:
            heappop(min_heap)

    return [num for _, num in min_heap]  # 공간 복잡도 계산 시 고려 X

질문 2 - 더 간결하고, 파이써닉한 풀이
책에 있는 파이썬다운 풀이

def topKFrequent(self, nums, k):
        return list(zip(*collections.Counter(nums).most_common(k)))[0]

이거는 딱히 질문이라기보다는, 이 풀이가 CP스러운 것 같아서 언패킹을 활용하지 않고도 이렇게 더 간결하게 쓸 수 있을 것 같아요.
👇

# 제 풀이
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return [num for num, _ in Counter(nums).most_common(k)]  # O(n log n) 시간 & O(n) 공간

읽어주셔서 감사합니다!

[likejazz]

안녕하세요~

책에서도 여러 차례 언급하고 있지만 log는 마법과 같은 함수라서 로그 뒤에 위치한 값이 무엇이느냐는 성능에 전혀 영향을 주지 않습니다. 왜냐면 log(1억)도 27도 채 안되기 때문이죠. 즉 n log(n)이나 n log(k)는 사실상 같다고 할 수 있습니다. 따라서 실무에서는 의미가 없다고 할 수 있고, 하지만 구두로 코딩 인터뷰를 진행할 때는 면접관에게 이 같은 내용을 설명할 수 있다면 당연히 더 좋은 인상을 줄 수는 있을 것 같습니다.

아울러 리스트 컴프리헨션으로 표현하니 훨씬 더 가독성이 좋은거 같네요. 감사합니다!

[nayeonshin]

안녕하세요 @likejazz 님 답변 감사합니다! 이해가 잘 되었어요.

한 가지 더 질문이 있어요. 여기서 O(n log n) 풀이를 O(n + k log n)으로 최적화하는 것은 "실무에서도 의미"가 있을까요?

답을 찾기 위해 시도해본 것

is "k log n" smaller than "n log n" in big o for k <= n이런 키워드로 구글링을 해보고, 몇 개 없는 관련 검색 결과 중 스택오버플로우 글 몇 개를 읽어봤는데: 글 1, 글 2 약간 상충되는 내용이 있는 것 같아서 헷갈립니다. 👇

글 1 답변: "O(n + (k log n)) is approximately O(n)" (제 해석: O(n + (k log n)) ≈ O(n))
vs.
글 2 답변: "Which is "better" is therefore unclear, although my quick analysis tended to show that O(n + k log n) performs better under mild assumptions on k." (제 해석: "결국 O(n + k log n)과 O(n log n) 중 어떤 것이 더 나은 지는 불분명하다")

---

최대힙을 사용하는 책의 코드에서 로그 앞에 있는 계수를 최적화할 수 있는 방법(O(n log n) 풀이를 O(n + k log n)로)을 생각해봤어요.

책의 코드는 비어있는 리스트를 먼저 선언하고, 힙(리스트)에 요소를 하나씩 삽입하면서 힙을 쌓아가기 때문에 최종적으로 이 풀이의 시간 복잡도는, n이 len(nums)일 때, O(n + n log (n) + k log (n)) = O(n log (n)) ➡️ 아래 코드 항목 참조
(문제에 k는 최대 n이라는 constraint이 존재하기 때문에 O(k log (n)) <= O(n log (n)), 따라서 단순히 O(n log (n)으로 표기 가능)이지만,

힙에 요소를 하나씩 넣는 것 대신 heapify()를 사용하면 힙을 만드는 시간 복잡도가 O(n log n)에서 O(n)으로 줄기 때문에, 총 시간 복잡도가 O(n + n + k log (n)) = O(n + k log (n))입니다. 여기에다가 사소한 edge case인 if k == len(nums): return nums 체크를 통해 k == n인 경우를 미연에 방지하여 k가 n보다 엄격히 작을 수 있도록 보장한다면,
이런 O(n log (n) ⇒ O(n + k log (n)) 시간 복잡도 최적화가 의미가 있다고 볼 수 있을까요? (이런 최적화가 "polynomially dominating"하는 항을 최적화하는 것일까요?)

코드

책에 있는 원래 코드

def topKFrequent(self, nums: List[int], k: int) -> List[int]: freqs = collections.Counter(nums) # O(n) 시간 & O(n) 공간 (여기서 `n`은 len(nums)) freqs_heap = [] for f in freqs: # ⭐ 힙에 요소를 하나씩 삽입함으로써 최대힙을 쌓기 때문에 O(n log n) 시간 heapq.heappush(freqs_heap, (-freqs[f], f)) # `freq_heap`: O(n log n) 시간 & O(n) 공간

    topk = list()
    for _ in range(k):
        # 아웃풋 리스트인 `topk`를 공간 복잡도 계산에 고려하지 않았을 때, O(k log n) 시간 & O(1) 공간
        topk.append(heapq.heappop(freqs_heap)[1])

    return topk

👇

heapify()를 사용해 최적화한 코드

def topKFrequent(self, nums: List[int], k: int) -> List[int]: if len(nums) == k: # ⭐ 최적화 방법: edge case 체크하여 k < n을 엄격히 보장 return nums

    freqs = collections.Counter(nums)  # O(n) 시간 & O(n) 공간 (여기서 `n`은 len(nums))
    
    # ⭐ 최적화 방법: 미리 튜플 리스트를 만들고 heapify()를 한번에 하기 -- O(n) 시간 & O(n) 공간 =====
    freqs_heap = [(-freqs[f], f) for f in freqs]  # O(n) 시간 & O(n) 공간
    heapify(freqs_heap)  # O(n) 시간 & O(1) 공간
    # ==========

    topk = list()
    for _ in range(k):
        # 아웃풋 리스트인 `topk`를 공간 복잡도 계산에 고려하지 않았을 때, O(k log n) 시간 & O(1) 공간
        topk.append(heapq.heappop(freqs_heap)[1])

    return topk

제 질문이 별로 중요하지 않은 질문일 수도 있지만, 긴 글 읽어주셔서 정말정말 감사합니다!

+) 코드 섹션 HTML 렌더링이 약간 이상하게 되네요. 이해 부탁드립니다. ㅠㅠ