[ Python ] Collections - Counter, defaultdict

프로그래머스에서 숫자짝꿍 문제를 해결하고 다른 사람들의 풀이를 봤는데

처음 들어보는 Collection 패키지의 Counter와 defaultdict 객체를 사용한 풀이들이 눈에 보였다.

# 이건 내 풀이
def solution(X, Y):
    
    nums = []
    for n in set(X) & set(Y) :
        for i in range(min(X.count(n), Y.count(n))) :
            nums.append(n)
    if nums == [] :
        return "-1"
    else :
        if max([n != "0" for n in nums]) == 0 :
            return "0"
        return "".join(sorted(nums, reverse=True))

# 다른 사람의 풀이
from collections import Counter, defaultdict
def solution(X, Y):
    x, y = list(X), list(Y)
    arr = []
    answer = ""

    c_x, c_y = Counter(x) , Counter(y)
    for key in c_x.keys():
        if key in c_y.keys():
            arr.append((int(key), min(c_x[key], c_y[key])))

    if not arr:
        return "-1"
    elif len(arr) == 1 and arr[0][0] == 0:
        return "0"

    arr = sorted(arr, key = lambda x : x[0], reverse= True)

    for ar in arr:
        answer += str(ar[0]) * int(ar[1])
    return answer

# defaultdict만 사용한 다른 사람 풀이
from collections import defaultdict
def solution(X, Y):
    d = defaultdict(int)
    temp = ''
    if len(X) < len(Y):
        X, Y = Y, X
    for i in X:
        d[i] += 1

    for j in Y:
        if d[j] > 0:
            d[j] -= 1
            temp += j
    if len(set(temp)) == 1 and temp[0] == '0':
        return '0'
    elif temp == '':
        return '-1'
    else:
        return ''.join(sorted(temp, reverse = True))

(처리 속도는 내가 쓴 코드 > defaultdict > Counter 순으로 빠른 것 같지만... )

처음 본 모듈들이라

이게 뭔지 찾아 보았다.

 

 

collections — Container datatypes

 

Collection - 컨테이너 데이터형

소스 코드 : Lib/collections/__init__.py

 

파이썬의 범용 내장 컨테이너 dict, list, set 및 tuple에 대한 대안을 제공하는 특수 컨테이너 데이터형을 구현합니다.

namedtuple() : 이름 붙은 필드를 갖는 튜플 서브 클래스를 만들기 위한 팩토리 함수

deque : 양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너

ChainMap : 여러 매핑의 단일 뷰를 만드는 딕셔너리류 클래스

Counter : 해시 가능한 객체를 세는 데 사용하는 딕셔너리 서브 클래스

OrderedDict : 항목이 추가된 순서를 기억하는 딕셔너리 서브 클래스

defaultdict : 누락된 값을 제공하기 위해 팩토리 함수를 호출하는 딕셔너리 서브 클래스

UserDict : 더 쉬운 딕셔너리 서브 클래싱을 위해 딕셔너리 객체를 감싸는 래퍼

UserList : 더 쉬운 리스트 서브 클래싱을 위해 리스트 객체를 감싸는 래퍼

UserString : 더 쉬운 문자열 서브 클래싱을 위해 문자열 객체를 감싸는 래퍼

 

Counter 객체

편리하고 빠르게 개수를 세도록 지원하는 counter 도구가 제공됩니다.

# Tally occurrences of words in a list
cnt = Counter()
for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
    cnt[word] += 1
cnt  # Counter({'blue': 3, 'red': 2, 'green': 1})

# Find the ten most common words in Hamlet
import re
words = re.findall(r'\w+', open('hamlet.txt').read().lower())
Counter(words).most_common(10)
# [('the', 1143), ('and', 966), ('to', 762), ('of', 669), ('i', 631), ('you', 554),  ('a', 546), ('my', 514), ('hamlet', 471), ('in', 451)]

Class Collections.Counter([iterable-or-mapping])

Counter는 해시 가능한 객체를 세기 위한 dict 서브 클래스입니다.

키: 딕셔너리 값 >> 요소: 개수(0과 음수를 포함하는 임의의 정수)

Counter클래스는 다른 언어의 백(bag)이나 멀티셋(multiset)과 유사합니다.

 

요소는 이터러블로부터 계산되거나 다른 매핑(또는 Counter)에서 초기화됩니다.

c = Counter()                           # a new, empty counter
c = Counter('gallahad')                 # a new counter from an iterable
c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
c = Counter(cats=4, dogs=8)             # a new counter from keyword args

계수기 객체는 아래 사항을 제외하고 딕셔너리 인터페이스를 갖습니다.

(누락된 항목에 대해 KeyError를 발생시키는 대신 0을 반환)

c = Counter(['eggs', 'ham'])
c['bacon']                              # 0 : count of a missing element is zero

개수를 0으로 설정해도 Counter에서 요소가 제거되지 않습니다.

완전히 제거하려면 del을 사용하십시오.

c['sausage'] = 0                        # counter entry with a zero count
del c['sausage']                        # del actually removes the entry

Counter는 dict subclass로서 삽입 순서를 기억할 수 있는 기능을 상속받았습니다.

Counter객체의 수학 연산 또한 순서를 보존합니다.

결과는 왼쪽 피연산자에서 요소가 처음 발생했을 때와 오른쪽 피연산자에서 발생한 순서에 따라 정렬됩니다.

Counter객체는 모든 dict에서 사용할 수 있는 메서드에 추가적으로 아래 메서드를 더 지원합니다.

 

elements()

개수만큼 반복되는 요소에 대한 이터레이터를 반환

요소는 처음 발견되는 순서대로 반환

요소의 개수가 1보다 작으면 무시

c = Counter(a=4, b=2, c=0, d=-2)
sorted(c.elements())  # ['a', 'a', 'a', 'a', 'b', 'b']

 

most_common([n])

n개의 가장 흔한 요소와 그 개수를 가장 흔한 것부터 가장 적은 것 순으로 나열한 리스트를 반환

n이 생략되거나 None이면 Counter의 모든 요소를 반환

개수가 같은 요소는 처음 발견된 순서를 유지함

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

 

subtract([iterable-or-mapping)]

이터러블이나 다른 매핑(또는 Counter)으로부터 온 요소들을 뺍니다.

dict.update()와 비슷하지만 교체하는 대신 개수를 뺍니다.

입력과 출력 모두 0이나 음수일 수 있습니다.

c = Counter(a=4, b=2, c=0, d=-2)
d = Counter(a=1, b=2, c=3, d=4)
c.subtract(d)
c  # Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})

 

total()

요소의 개수 총합을 계산합니다.

일반적인 딕셔너리 메서드를 Counter객체에 사용할 수 있지만, 두 메서드는 Counter에서 다르게 동작합니다.

c = Counter(a=10, b=5, c=0)
c.total()  # 15

 

fromkeys(iterable)

이 클래스 메서드는 Counter 객체에 구현되지 않았습니다.

 

update([iterable-or-mapping])

요소는 이터러블에서 세거나 다른 매핑(또는 Counter)에서 더해집니다.

dict.update()와 비슷하지만, 교체하는 대신 더합니다.

또한, 이터러블은 (key, value) 쌍의 시퀀스가 아닌, 요소의 시퀀스일 것으로 기대합니다.

 

카운터는 동일성, 부분 집합 및 초집합 관계에 대한 풍부한 비교 연산자를 지원합니다

: =, !=, <, <=, >, >==. 

이러한 비교 연산은 모두 결측 요소를 계수가 0인 것으로 처리합니다.

counter(a=1) == count(a=1, b=0)  # True

 

 

Counter 객체 사용 예시

c.total()                       # total of all counts
c.clear()                       # reset all counts
list(c)                         # list unique elements
set(c)                          # convert to a set
dict(c)                         # convert to a regular dictionary
c.items()                       # convert to a list of (elem, cnt) pairs
Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs
c.most_common()[:-n-1:-1]       # n least common elements
+c                              # remove zero and negative counts

 

카운터 객체를 결합하여 다중 집합(카운트가 0보다 큰 카운터)을 생성하기 위한 여러 수학적 연산이 제공됩니다. 덧셈과 뺄셈은 해당 요소의 개수를 더하거나 빼서 카운터를 결합한다. 교차점과 합집합은 해당 카운트의 최소값과 최대값을 반환합니다. 동일성과 포함은 해당 카운트를 비교합니다. 각 작업은 서명된 카운트가 있는 입력을 허용할 수 있지만, 카운트가 0 이하인 결과는 출력에서 제외됩니다.

c = Counter(a=3, b=1)
d = Counter(a=1, b=2)
c + d                       # add two counters together:  c[x] + d[x]
# Counter({'a': 4, 'b': 3})
c - d                       # subtract (keeping only positive counts)
# Counter({'a': 2})
c & d                       # intersection:  min(c[x], d[x])
# Counter({'a': 1, 'b': 1})
c | d                       # union:  max(c[x], d[x])
# Counter({'a': 3, 'b': 2})
c == d                      # equality:  c[x] == d[x]
# False
c <= d                      # inclusion:  c[x] <= d[x]
# False

 

단항 덧셈과 뺄셈은 빈 counter 객체를 더하거나 또는 빈 counter객체를 빼는 것의 줄임 표현입니다.

c = Counter(a=2, b=-4)
+c
# Counter({'a': 2})
-c
# Counter({'b': 4})

 

참고

Counter객체는 주로 양의 정수로 작동하여 횟수를 나타내도록 설계되었습니다.

그러나, 다른 형이나 음수 값이 필요한 사용 사례를 불필요하게 배제하지 않도록 주의를 기울였습니다.

이러한 사용 사례에 도움이 되도록, 이 절은 최소 범위와 형 제약 사항을 설명합니다.

• Counter 클래스 자체는 키와 값에 제한이 없는 딕셔너리 서브 클래스입니다. 값은 개수를 나타내는 숫자로 의도되었지만, 값 필드에 어떤 것이든 저장할 수 있습니다.
• most_common() 메서드는 값에 대해 순서만을 요구합니다.
• c[key] += 1과 같은 제자리 연산의 경우, 값 형은 덧셈과 뺄셈만 지원하면 됩니다. 따라서 분수(fractions), 부동 소수점(floats) 및 십진수(decimals)가 작동하고 음수 값이 지원됩니다. update()와 subtract()에 대해서도 마찬가지인데, 입력과 출력 모두 음수와 0을 허용합니다.
• multiset 메서드는 양의 값에 대한 사용 사례를 위해서만 설계되었습니다. 입력은 음수이거나 0일 수 있지만, 양수 값을 갖는 출력만 만들어집니다. 형 제한은 없지만, 값 형은 더하기, 빼기 및 비교를 지원해야 합니다.
• elements() 메서드는 정수 개수를 요구합니다. 0과 음수 개수는 무시합니다.

 

---

defaultdict 객체

class collections.defaultdict(default_factory=None, /[, ...])

 

 

defaultdict 사용 예시

list를 default_factory로 사용하면, 키-값 쌍의 시퀀스를 리스트의 딕셔너리로 쉽게 그룹화 할 수 있습니다:

s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
d = defaultdict(list)
for k, v in s:
    d[k].append(v)

sorted(d.items())  # [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

각 키가 처음 발견될 때, 아직 매핑에 있지 않게 됩니다.

그래서 default_factory 함수를 사용하여 항목이 자동으로 만들어지는데, 빈 list를 반환합니다.

그런 다음 list.append() 연산이 값을 새 리스트에 추가합니다.

키를 다시 만나면, 조회가 정상적으로 진행되고 (해당 키의 리스트를 반환합니다), 

list.append() 연산은 다른 값을 리스트에 추가합니다.

이 기법은 dict.setdefault()를 사용하는 동등한 기법보다 간단하고 빠릅니다.

d = {}
for k, v in s:
    d.setdefault(k, []).append(v)

sorted(d.items())  # [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

default_factory를 int로 설정하면 defaultdict를 세는(counting)데 유용하게 사용할 수 있습니다

(다른 언어의 백(bag)이나 멀티 셋(multiset)처럼)

s = 'mississippi'
d = defaultdict(int)
for k in s:
    d[k] += 1

sorted(d.items())  # [('i', 4), ('m', 1), ('p', 2), ('s', 4)]

글자가 처음 발견될 때, 매핑에서 누락되었으므로, default_factory함수는 int()를 호출하여 기본 계수 0을 제공합니다.

증분 연산은 각 문자의 개수를 쌓아나갑니다.

항상 0을 반환하는 함수 int()는 상수 함수의 특별한 경우일 뿐입니다.

상수 함수를 만드는 더 빠르고 유연한 방법은 (단지 0이 아니라) 임의의 상숫값을 제공 할 수 있는 람다 함수를 사용하는 것입니다.

def constant_factory(value):
    return lambda: value
d = defaultdict(constant_factory('<missing>'))
d.update(name='John', action='ran')
'%(name)s %(action)s to %(object)s' % d  # 'John ran to <missing>'

default_factory를 set으로 설정하면, defaultdict를 집합의 딕셔너리를 만드는 데 유용하게 만듭니다.

s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)]
d = defaultdict(set)
for k, v in s:
    d[k].add(v)

sorted(d.items())  # [('blue', {2, 4}), ('red', {1, 3})]

 

---

 

collections 패키지의 Counter, defaultdict를 공부한 후,

다시 써 본 코딩

(defaultdict는 안써도 될 것 같아서 Counter객체만 사용해 보았다.)

from collections import Counter

def solution(X, Y):
    
    x, y = Counter(X), Counter(Y)
    answer = sorted((x & y).elements(), reverse=True)

    if answer == [] :
        return "-1"
    elif set(answer) == {"0"} :
        return "0"
    else :
        return "".join(answer)

# 이번엔 삼항연산자를 사용해 보았다.
from collections import Counter

def solution(X, Y):
    
    x, y = Counter(X), Counter(Y)
    answer = sorted((x & y).elements(), reverse=True)

    return "-1" if answer == [] else "0" if set(answer) == {"0"} else "".join(answer)

부분적으로 조금 느려졌지만 테스트 케이스 10 ~ 15번이 많이 빨라졌다.

코드를 다시 써 보긴 했지만 맨 처음 import 없이 그냥 쓴 코드가 내가 쓴 코드 중엔 제일 나은 것 같다.