[Python 파이썬] 프로그래머스 - 귤 고르기

2024년 8월 6일

문제 링크 : 프로그래머스 - 귤 고르기

---

문제 접근

 

그리디하게 접근해 간단하게 풀 수 있는 문제라고 판단했다. 

 

각 귤마다 이산 값을 가지며, 상자 하나에 k개의 귤을 담고자 할 때 귤의 크기 종류가 최소가 되도록 하고 싶으므로

각 크기 별 귤의 개수를 딕셔너리에 저장해 각 value 값을 리스트 형태로 뽑아와 내림차순 정렬하여 종류가 많은 귤부터 상자에 넣으면 된다고 결론냈다. 

 

k = 6, tangerine = [1, 3, 2, 5, 4, 5, 2, 3] 인 입력 예시를 들어보자.

 

각 크기별 개수를 딕셔너리 형태로 담아내면 다음과 같다.

 

dict = {1 : 1, 2 : 2, 3 : 2, 4 : 1, 5 : 2}

 

각 value 값을 리스트 형태로 뽑아내면 다음과 같다.

 

[1, 2, 2, 1, 2]

 

이를 내림차순으로 정렬하면 다음과 같다.

 

[2, 2, 2, 1, 1]

 

각 무게 별 개수가 많은 귤부터 상자에 먼저 담아야 종류가 최소가 되도록 담을 수 있으므로, 리스트의 맨 앞에서부터 값을 k로부터 빼며, k가 0 이하가 되면 더 이상 상자에 그만 담도록 로직을 구성하면 된다.

 

리스트의 각 요소를 탐색할 때마다 result를 1씩 증가시켜주며, 로직이 끝났을 때의 result가 원하는 답이 된다.

---

 

전체 코드

 

def solution(k, tangerine):
    answer = 0

    dict = {}
    for idx in range(len(tangerine)):
        if tangerine[idx] in dict:
            dict[tangerine[idx]] += 1
        else:
            dict[tangerine[idx]] = 1

    sorted_by_cnt = []

    for _, value in dict.items():
        sorted_by_cnt.append(value)

    # 내림차순 정렬
    sorted_by_cnt.sort(reverse=True)

    for cnt in sorted_by_cnt:
        k -= cnt
        answer += 1
        if k <= 0:
            break

    return answer

if __name__ == "__main__":
    print(solution(6, [1, 3, 2, 5, 4, 5, 2, 3]))

---

풀이 후기

 

그리디하게 풀 수 있는 간단한 문제였다.