Search: 10816 [Counter]

이전 풀이
이전 풀이에 있어서 시간복잡도 제약으로 실패한 바...
시간 복잡도를 줄이기 위해 HashMap기반의 Counter라이브러리를 활용해 보자
Hash와 HashMap

Counter 클래스

Counter 클래스는 파이썬의 collections 모듈에 포함된 해시맵 기반의 서브클래스이다. 주로 항목의 등장 횟수를 계산하고 저장하는 데 사용된다. 이는 리스트, 튜플, 문자열과 같은 반복 가능한(iterable) 객체를 받아서 각 항목의 빈도수를 세는 작업에 유용하다. 기본적으로 Counter는 딕셔너리 형태로 각 항목의 빈도를 저장하며, 이를 통해 다양한 연산을 효율적으로 처리할 수 있다.

1. Counter의 기본 사용법

Counter 클래스는 입력된 데이터에서 각 항목이 등장한 횟수를 계산하여 dict와 유사한 구조로 반환한다. 이를 통해 항목들의 빈도를 쉽게 파악할 수 있다.

from collections import Counter

cards = [6, 3, 2, 10, 10, 10, -10, -10, 7, 3]
counter = Counter(cards)

print(counter)

출력:

Counter({10: 3, 3: 2, -10: 2, 6: 1, 2: 1, 7: 1})

위 예시에서 cards 리스트에 등장한 각 숫자의 빈도를 계산하여 Counter 객체를 생성하였다. Counter 객체는 각 항목의 등장 횟수를 저장하며, 딕셔너리처럼 사용할 수 있다. 예를 들어, 10은 3번, 3은 2번 등장한다.

2. 주요 메서드와 속성

Counter 클래스는 데이터를 세는 것 외에도 다양한 기능을 제공한다. 주요 메서드 및 속성은 다음과 같다.

elements()

elements() 메서드는 등장 횟수가 반영된 항목들을 반복 가능한 형태로 반환한다. 이 메서드는 항목이 등장한 횟수만큼 요소를 반환하며, 음수 값은 무시한다.

counter = Counter([1, 2, 2, 3, 3, 3])
print(list(counter.elements()))  # [1, 2, 2, 3, 3, 3, 3]

이 메서드는 항목이 나타나는 순서대로 그 항목들을 반환한다.

most_common(n)

most_common(n) 메서드는 등장 횟수가 많은 n개의 항목을 튜플 형태로 반환한다. 항목은 내림차순으로 정렬되어 반환된다.

counter = Counter([1, 2, 2, 3, 3, 3])
print(counter.most_common(2))  # [(3, 3), (2, 2)]

이 메서드는 데이터의 상위 n개 항목을 추출할 때 유용하다.

subtract()

subtract() 메서드는 다른 iterable이나 Counter 객체를 인자로 받아서 해당 항목들의 빈도를 빼는 연산을 수행한다.

counter = Counter([1, 2, 3])
counter.subtract([1, 1, 3])
print(counter)  # Counter({2: 1, 3: 0, 1: -1})

음수 값을 결과로 가질 수 있으며, 이 메서드는 데이터를 감소시키는 데 사용된다.

update()

update() 메서드는 다른 iterable이나 딕셔너리를 사용하여 카운트를 갱신하는 데 사용된다.

counter = Counter([1, 2])
counter.update([2, 3, 3])
print(counter)  # Counter({2: 2, 3: 2, 1: 1})

기존의 카운트에 새로운 값을 더하는 기능을 제공한다.

total()

이런건 없다 ㅋㅋ 대신 sum(counter.values())를 사용하여 총합을 구할 수 있다.

counter = Counter([1, 2, 3])
total = sum(counter.values())
print(total)  # 6

3. 연산

Counter 객체 간에는 다양한 연산을 수행할 수 있다. 이들 연산은 기본적인 산술 연산과 같은 방식으로 작동한다.

덧셈 (+)

두 Counter 객체를 더하면 항목들의 빈도가 합쳐진 새로운 Counter 객체를 반환한다.

counter1 = Counter([1, 2, 3])
counter2 = Counter([3, 3, 4])
result = counter1 + counter2
print(result)  # Counter({3: 4, 1: 1, 2: 1, 4: 1})

이 연산은 각 항목에 대해 등장 횟수를 합산하여 새로운 Counter를 만든다.

뺄셈 (-)

Counter 객체끼리 뺄셈을 하면 첫 번째 Counter에서 두 번째 Counter의 항목들을 뺀 결과를 반환한다.

counter1 = Counter([1, 2, 3])
counter2 = Counter([3, 3, 4])
result = counter1 - counter2
print(result)  # Counter({1: 1, 2: 1})

뺄셈 연산은 음수 항목은 제거하며, 남은 항목들의 빈도수를 계산한다.

교집합 (&)

& 연산자는 두 Counter 객체의 교집합을 구한다. 이때, 교집합의 빈도는 각 Counter에서 가장 작은 빈도를 선택한다.

counter1 = Counter([1, 2, 3])
counter2 = Counter([3, 3, 4])
result = counter1 & counter2
print(result)  # Counter({3: 1})

교집합 연산은 두 Counter의 공통 항목만 반환한다.

합집합 (|)

| 연산자는 두 Counter 객체의 합집합을 구한다.

counter1 = Counter([1, 2, 3])
counter2 = Counter([3, 3, 4])
result = counter1 | counter2
print(result)  # Counter({3: 3, 1: 1, 2: 1, 4: 1})

4. 시간 복잡도

Counter는 해시맵을 사용하여 항목을 세기 때문에, 대부분의 연산은 O(1)의 시간 복잡도를 가진다. 예를 들어, elements(), most_common(), subtract(), update() 등의 메서드는 반복문을 사용하기 때문에 O(n)의 시간이 소요된다. 또한, 두 Counter 객체 간의 연산은 각 객체의 크기에 따라 O(n + m)의 시간이 걸린다.

5. 활용 예시

1. 리스트에서 요소의 빈도수 구하기

from collections import Counter

cards = [6, 3, 2, 10, 10, 10, -10, -10, 7, 3]
counter = Counter(cards)
print(counter)  # Counter({10: 3, 3: 2, -10: 2, 6: 1, 2: 1, 7: 1})

2. 가장 빈번한 두 항목 구하기

from collections import Counter

cards = [6, 3, 2, 10, 10, 10, -10, -10, 7, 3]
counter = Counter(cards)
print(counter.most_common(2))  # [(10, 3), (3, 2)]

3. 문자열에서 각 문자 빈도 구하기

from collections import Counter

word = "aabbccddeeff"
counter = Counter(word)
print(counter)  # Counter({'a': 2, 'b': 2, 'c': 2, 'd': 2, 'e': 2, 'f': 2})

6. 결론

Counter는 데이터의 빈도를 세고 처리하는 데 매우 유용한 도구로써 뭔가를 세거나, 빈도수를 계산해야할 때 사용하면 좋다!
더불어 Counter 객체 상호간 연산을 지원하는 것도 매우 유용하다!