collections 모듈의 Counter
- 불러오기
from collections import Counter- 사용하기
k = [1, 2, 3, 4, 5, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 7, 8]
Counter(k)- 결과
Counter({1: 1, 2: 1, 3: 1, 4: 1, 5: 4, 6: 1, 7: 7, 8: 1})리스트의 원소 별 개수를 딕셔너리 형태로 반환한다.
count()와의 차이
count() 예시 코드
dict = {i: tangerine.count(i) for i in set(tangerine)}시간 복잡도
- count()
: for문으로 리스트(집합)의 모든 요소 순회 * 각 요소의 개수를 카운트하기 위해 순회 = O(N^2) - Counter()
: 리스트를 전체적으로 한번에 훑어서 딕셔너리 형태로 각 원소의 개수를 반환 = O(N)
문제 풀어보기
문제
경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.
예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.
경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
접근
각 종류의 귤이 몇 개씩 있는지 구한 후, 가장 큰 개수부터 더해서 k개 이상이 되면 멈춘다.
코드
def solution(k, tangerine):
from collections import Counter
dict = Counter(tangerine)
if any(v >= k for v in dict.values()):
return 1
else:
count = 0
values = list(dict.values())
values.sort(reverse = True)
sums = values[0]
for i in range(1, len(values)+1):
sums += values[i]
if sums >= k:
return i + 1
- collections의 counter로 사전을 만드는 것이 관건이었다. for문과 count를 이용해 코드를 작성하면 시간초과가 뜬다.
To Dare is To Do