[python] 프로그래머스 Lv2. - 귤 고르기

코딩테스트 연습 - 귤 고르기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

처음 문제를 보고 든 생각은

조합을 이용해 풀면 되지 않나? 였으나.. 그렇게 쉽게 풀릴리가 없지.

테케는 다 통과하지만 바로 시간초과에 걸려버렸다.

 

[처음 코드]

from itertools import combinations

def solution(k, tangerine)
    answer=100001
    
    for com in combinations(tangerine, k):
        x=set(com)
        if answer > len(x):
        	answer=len(x)
    return answer

중복 되는 부분에서 브레이크 처리를 해줘야하나 고민하다

시간 복잡도가 줄어들지 않을 것 같아서

 

아예 딕셔너리를 활용하기로 했다.

 

[수정 코드]

from itertools import combinations

def solution(k, tangerine):
    answer = 0
    dic={}
    for i in tangerine:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] +=1
            
    v=[]
    for val in dic.values():
        v.append(val)
    
    v.sort(reverse=True)
    
    for i in range(len(v)):
        k=k-v[i]
        answer+=1
        if k<=0:
            break
        
    return answer

각 원소의 개수를 딕셔너리에 담은 후 value 값들을 내림차순 정렬한다.

그리고 구하려는 귤의 개수를 value 값을 빼주며 줄여나가고 answer의 값을 +1 해준다.

귤의 개수가 0이나 음수가 되어 더 이상 세지 않아도 된다면 중단한다.

 

다른 코드를 참고하다가 collections 모듈의 counter를 사용하여 원소의 개수를 구한 코드를

발견하였다.

익숙하지 않아서 사용하지 않았었는데 이참에 다시 정리해봐야겠다.

 

[참고코드]

import collections

def solution(k, tangerine):
    answer = 0
    cnt = collections.Counter(tangerine)

    for v in sorted(cnt.values(), reverse = True):
        k -= v
        answer += 1
        if k <= 0:
            break
    return answer

 

 

2023.06.30 - [컴퓨터/python] - [python] collections 모듈 - Counter