귤 고르기

프로그래머스 lv2 귤 고르기 파이썬

💡 문제

경화가 한 상자에 담으려는 귤의 개수 k와
귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다.
경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 
return 하도록 solution 함수를 작성해주세요.

🥳 해결

생각

1. 원소의 길이 제한사항이 작으니 dictionary도 괜찮을듯?
2. Counter 함수 사용? 하면 해결이 될것 같다.
3. 런타임을 줄일 방법을 찾을 것.
4. Counter 자체를 for문으로 돌릴까?

생각을 먼저 하는 습관을 들이는게 알고리즘에서 도움이 된것 같다.
길이의 제한사항은 작으니 for문으로 돌려도 괜찮겠다는 판단이 들었다.

코드

from collections import Counter
def solution(k, tangerine):
    x = 0
    cnt = 0
    for i,j in Counter(tangerine).most_common(k): # 상위 n개의 원소 출력
        x += j # 원소의 총 개수 저장
        cnt += 1 # 단일 원소 개수 저장
        if x >= k: 
            return cnt

상위 n개의 원소를 뽑아주는 Counter.most_common() 함수가 먼저 생각났고, 그걸 리스트로 append 하고 sum()을 쓰는 방법도 있겠지만
런타임이 너무 오래걸릴것 같아 단순히 더해줬다.

상위 n개를 k로 고른 이유는 전부 1일 경우 최대가 k개 이기 때문에 그렇게 정해줬다.

간단하게 하나 해결!🥳🥳🥳

🥳 다른 해결

for문으로만 혹은, 길이도 짧은데 dictionary로 해결이 안될까..?🤔
싶어서 이번엔 다르게 풀어봤다.

코드

def solution(k, tangerine):
    tan_dict = {}
    cnt = 0
    
    for i in set(tangerine):
        tan_dict[i] = 0 # 딕셔너리 생성
    
    for i in tangerine:
        tan_dict[i] += 1 # 딕셔너리에 값 생성, 저장
    
    counts = sorted((i for i in tan_dict.values()), reverse = True) 
    # 개수만 저장 후 sort
    
    for i,j in enumerate(counts): # 인덱스와 같이 for문으로 돌리기
        cnt += j
        if cnt >= k:
            return i+1

중복을 없애기 위해서 set로 바꾼후 dictionary를 만들어 줬다.

그 후 값들만 저장 후 for문에 돌리기 위해
미리 sorted(,reverse = True) 해주었다.

특히 여기 부분은 runtime 문제 해결을 위해 일부러 제네레이터 형식으로 코드를 짜봤다. (근데 list가 더 빨랐음;;; 왜지 값이 작아서 그런가 아시는 분은 댓글 부탁드립니다.)

그리고 enumerate를 통해 값과 인덱스를 같이 넘겼다.

참고로 옆에 for i,j in enumerate(counts, start = 1):
식으로 시작 값을 저장하면 추후에 i+1을 안해줘도 된다.

끝!