[프로그래머스] 완주하지 못한 선수. Counter 객체 분석

내 코드

from collections import defaultdict
def solution(participant, completion):
    d = defaultdict(int)
    for p in participant: d[p]+=1
    for c in completion: d[c]-=1
    return [x for x in d if d[x]!=0][0]

다른 사람 풀이

• Counter 객체를 썼는데 좋아보였다.

파이썬 Counter 공식문서

from collections import Counter
def solution(participant, completion):
    p = Counter(participant)
    c = Counter(completion)
    p-=c
    return [*p.keys()][0]

• 이렇게 간단하게 counting을 할 수 있다.
• 문서를 보면 most_common(), total() 등 유용한 함수를 제공한다.

라이브러리 뜯어보기

• Counter의 시간 복잡도를 알아보다가 코드를 찾아보게 되었다.
• Cpython, Counter 구현 코드

 def most_common(self, n=None):
        '''List the n most common elements and their counts from the most
        common to the least.  If n is None, then list all element counts.

        >>> Counter('abracadabra').most_common(3)
        [('a', 5), ('b', 2), ('r', 2)]

        '''
        # Emulate Bag.sortedByCount from Smalltalk
        if n is None:
            return sorted(self.items(), key=_itemgetter(1), reverse=True)
        return _heapq.nlargest(n, self.items(), key=_itemgetter(1))

• 내부적으로 heapq의 nlargest를 사용하고 있다.
• Cpython heapq 구현코드

def nlargest(n, iterable, key=None):
    """Find the n largest elements in a dataset.

    Equivalent to:  sorted(iterable, key=key, reverse=True)[:n]
    """
		# 중략

    # When key is none, use simpler decoration
    if key is None:
        it = iter(iterable)
        result = [(elem, i) for i, elem in zip(range(0, -n, -1), it)]
        if not result:
            return result
        heapify(result)
        top = result[0][0]
        order = -n
        _heapreplace = heapreplace
        for elem in it:
            if top < elem:
                _heapreplace(result, (elem, order))
                top, _order = result[0]
                order -= 1
        result.sort(reverse=True)
        return [elem for (elem, order) in result]

• nlargest는 n(전체 크기 N과 구분)이 size보다 크거나 같은경우는 sorted를 사용하여 O(NlogN) 시간을 쓴다. (중략된 부분)
• n이 작은 size보다 작은 경우 전체를 heapify하지 않고 첫 n부분만 가져와서 나머지 부분을 heap으로 replace 한다.
  • heapreplace는 새로운 값을 넣고, 작은수는 내보낸다. 결과적으로 힙 크기는 유지된다.
• 시간복잡도를 과정별로 분석하면
  • O(n) - iter에서 배열을 가져오는 부분
  • O(n) - heapify (여기에 대해서도 곧 다뤄야겠다.)
  • O((N-n)logn) - 큰 값인지 비교하며 heapreplace
  • O(nlogn) - 마지막 sort
• 최종적으로 O(Nlogn). n이 1일때는 O(n)이다.
  • n=1일때 max 연산과 같은 복잡도지만 오버헤드 등 내부 연산이 있기 때문에, nlargest에서는 그냥 n=1일 때 실제로 max연산을 한다.
  • 그냥 sort 연산 후 앞부분만 취하는 것(O(NlogN)과는 확연한 차이다.