[Python] 프로그래머스, 귤 고르기 Lv.2 (feat.Counter, enumerate, 파이썬)

반짝반짝 알고리즘, 인프준

 

 

 

 

귤 고르기

문제 링크

프로그래머스

 

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

 

예를 들어, 경화가 수확한 귤 8개의 크기가 [ 1, 3, 2, 5, 4, 5, 2, 3 ]이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

 

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

 

제한 조건

• 1 <= k <= tangerine의 길이 <= 100,000
• 1 <= tangerine의 원소 <= 10,000,000

 

 

입출력 예

k	tangerine	result
6	[ 1, 3, 2, 5, 4, 5, 2, 3 ]	3
4	[ 1, 3, 2, 5, 4, 5, 2, 3 ]	2
2	[ 1, 1, 1, 1, 2, 2, 2, 3 ]	1

 

입출력 예 설명

입출력 예#1

본문에서 설명한 예시입니다.

 

입출력 예#2

경화는 크기가 '2인 귤 2개와 3인 귤 2개' 또는 '2인 귤 2개와 5인 귤 2개' 또는 '3인 귤 2개와 5인 귤 2개'로 귤을 판매할 수 있습니다. 이때의 크기 종류는 2가지로 이 값이 최소가 됩니다. 

 

입출력 예#3

경화는 크기가 1인 귤 2개를 판매하거나 2인 귤 2개를 판매할 수 있습니다. 이때의 크기 종류는 1가지로, 이 값이 최소가 됩니다.

 

 

해결 과정

 

1. 먼저 크기별 수량을 확인하기 위해 collections 모듈의 Counter 함수를 사용하였습니다. 딕셔너리 형태로 반환된 값을 sorted함수를 통해 value값을 기준으로 내림차순 정렬하였습니다.

class collections.Counter([iterable-or-mapping])

'''
Counter는 해시 가능한 객체를 세기 위한 dict 서브 클래스입니다.
요소가 딕셔너리 키로 저장되고 개수가 딕셔너리값으로 저장되는 컬렉션입니다.
개수는 0이나 음수를 포함하는 임의의 정숫값이 될 수 있습니다.
Counter 클래스는 다른 언어의 백(bag)이나 멀티 셋(multiset)과 유사합니다.

출처: https://docs.python.org/
'''

{'A':6, 'B':3, 'C':9}

>>> sorted(x, key=x.get, reverse=True)
['C', 'A', 'B']

>>> sorted(x.items(), key=lambda pair: pair[1], reverse=True)
[('C', 9), ('A', 6), ('B', 3)]

 

 

 

2. 그리고 정렬된 목록으로 for loop을 돌립니다. 결과 값 리턴을 위해 'enumerate'함수를 사용하여 인덱스 값도 가져오며 1부터 시작하기 위해 'start=1'을 작성합니다.

enumerate(iterable, start=0)

'''
열거 객체를 돌려줍니다.
iterable 은 시퀀스, 이터레이터 또는 이터레이션을 지원하는 다른 객체여야 합니다.
enumerate() 에 의해 반환된 이터레이터의 __next__() 메서드는
카운트 (기본값 0을 갖는 start 부터)와 iterable 을 이터레이션 해서
얻어지는 값을 포함하는 튜플을 돌려줍니다.

출처: https://docs.python.org/
'''

 

 

최종 코드

from collections import Counter
def solution(k, tangerine):
    # 귤 크기별 수량에 따른 정렬
    sort_list = sorted(Counter(tangerine).items(), key=lambda pair: pair[1], reverse=True)
    
    # '종류 수'와 '종류 별 수량' for loop
    for i, t in enumerate(sort_list, start=1):
        # 수량이 많은 귤부터 담기
        k -= t[1]
        # 상자가 가득차면 담은 횟수(인덱스) 리턴
        if(k <= 0):
            return i

 

 

 

또 다른 풀이

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

 

 

방식은 유사하지만 dictionary의 values으로 바로 처리하는 방법입니다. answer 변수를 별도로 정의해줘야 하는 차이가 있지만 코드가 더욱 간결해져 가독성이 높아집니다.

 

 

 

 

 

 

---

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges