이번에 살펴볼 자료구조는 Counter라는 dictionary의 일종인 자료구조입니다. 이름에서 알 수 있듯이, 이 Counter는 특히나 어떤 item을 count하는 데에 특화되어 있습니다. 이것은 collections라는 라이브러리 안에 존재하는 자료구조이므로 반드시 import해 주셔야 합니다.

from collections import Counter
from operator import itemgetter

그럼 먼저 3, 8, 10이 각각 5개씩 들어있는 A라는 리스트를 가정해 보겠습니다. Counter의 강력한 생성자 덕분에 이 리스트의 원소들을 각각 count하여 원소들을 key로, 등장하는 횟수를 value로 하여 dictionary를 만들 수 있습니다. 또한 Counter는 key가 정의되지 않는 상태에서 숫자 연산을 하더라도, default값을 0으로 지니고 있기 때문에 keyError가 나지 않습니다. 이런 면에서 기본 dictionary보다 편리하죠 :)

먼저 아까 가정한 A라는 리스트를 만들어 보겠습니다.

>>> A = [10]*5 + [8]*5 + [3]*5
>>> print A
[10, 10, 10, 10, 10, 8, 8, 8, 8, 8, 3, 3, 3, 3, 3]

Counter의 유용한 생성자를 이용하면 손쉽게 count할 수 있습니다.

>>> C = Counter(A)
>>> print C
Counter({8: 5, 10: 5, 3: 5})

참고로 dictionary는 hash map 구조를 가지기 때문에 key가 정렬되어 있지 않습니다! 기본적으로 dictionary에는 .keys()라는 key들을 리스트로 리턴하는 함수, .values()라는 value들을 리스트로 리턴하는 함수, 마지막으로 .items()라는 key-value pair들을 리스트로 리턴하는 함수가 존재합니다.

>>> print C.keys()
[8, 10, 3]
>>> print C.values()
[5, 5, 5]
>>> print C.items()
[(8, 5), (10, 5), (3, 5)]

그럼 이제 다음과 같은 상황을 가정해 봅시다. 만약 우리가 value에 대해서는 내림차순으로 정렬하고 싶고, key에 대해서는 오름차순으로 정렬하고 싶으면 어떻게 해야 할까요? 다양한 방법들이 존재하겠지만, 일단 가장 간단한 방법은 각각의 경우에 대해서 정렬을 시행해 주면 됩니다. 즉, 독립적으로 key에 대해서 한번, value에 대해서 한번 정렬해주는 방법입니다. 이것이 가능한 이유는 정렬을 하면서 swap할 때에 기존에 있던 동점자의 위치를 보존해주기 때문입니다!

>>> sorted_C = sorted(C.items(), key=itemgetter(1), reverse=True) #먼저 value에 대해서 내림차순 정렬해줍니다.
>>> print sorted_C
[(8, 5), (10, 5), (3, 5)] ##보시면 아시겠지만 위의 key의 순서를 그대로 보존하고 있죠?

>>> sorted_C = sorted(sorted_C) #다음으로 key에 대해서 오름차순 정렬해줍니다.
>>> print sorted_C
[(3, 5), (8, 5), (10, 5)]

그런데 여기서 조금 더 고급스럽게(?) 정렬하는 방법이 있습니다. 바로 우리가 정렬할 때 사용하는 함수를 직접 정의해 주는 방법입니다. 위의 똑같은 기능을 하는 코드를 작성해 보겠습니다.

>>> sorted_C_union = sorted(C.items(), key=lambda x: (-x[1], x[0]))
>>> print sorted_C_union
[(3, 5), (8, 5), (10, 5)]

key라는 인자는 어떤 것을 정렬할지 얘기하는데, 그 부분에 lambda함수를 사용하여 tuple을 정렬하게끔 합니다. 그 tuple은 -value를 첫번째 원소로, key를 두번째 원소로 가짐으로써 tuple을 오름차순 정렬했을 때, 자연스럽게 value가 먼저 내림차순으로 정렬되고, 동점일 경우 key를 오름차순으로 정렬하게 됩니다.

그럼 이제 list를 인자로 받는 함수를 하나 정의해서 문제(출처 : Codechef)를 풀어봅시다.

def maxOccur(A):
    count = Counter(A)
    sorted_count = sorted(count.items(), key=lambda x: (-x[1], x[0]))
    return sorted_count[0]

>>> print maxOccur([1,2,3,2,5])
(2, 2)
>>> print maxOccur([1,2,2,1,1,2])
(1, 3)

상대적으로 고급언어인 python의 강력한 built-in 기능들을 잘 활용하는 법을 연습합시다 :)