🍊 귤을 수확하여 k 개를 골라 상자에 담아 팔려고 한다
그런데 귤 크기가 일정하지 않으니 보기 좋지 않아서 최대한 크기가 같은 것을 담으려고 한다
서로 다른 크기 종류를 최소화 했을때 담기는 종류의 수를 구하는 문제이다!
우선 k와 총 귤 갯수의 범위가..
1<=k<= 🍊 <=100,000 이며,, 1<=🍊<=10,000,000 이다..! 꽤 크다!
우선 이 문제는 보아하니..
각 귤의 수를 체크해두고 정렬한 후 k개 까지 역순으로 담다가 중단하면 되겠다!
그래서 처음에
tcount = sorted([tangerine.count(t) for t in list(set(tangerine))])[::-1]이렇게 단순히 카운트 함수를 썼는데!!
시간에러! 가 ! 또 났다!!
요 count 함수가 시간복잡도가 높은 함수라고 한다.. 😭
그래서 dictionary 를 이용하여 카운트를 세주는 방식으로 변경하였다..
최종 코드는 이렇다!
def solution(k, tangerine):
tcount={}
# 카운트 체크
for t in tangerine:
if not t in tcount:
tcount[t]=0
tcount[t]+=1
# 카운트(value) 값으로 역정렬
sort_count = sorted(tcount.items(),key=lambda x:x[1],reverse=True)
tsum=0
# k 만큼 담기
for ti,c in enumerate(sort_count):
tsum+=c[1]
if tsum>=k:
return ti+1
다른 문제보다는 쉬웠던 문제다! count 가 굉장히 느리다는것도 배웠고
