[Programmers] LV 2. 귤 고르기 - 138476 (Python 파이썬)

프로그래머스, 귤 고르기 - 138476 파이썬(Python) 풀이

 

안녕하세요. 프로그래머스 Level 2 문제인 '귤 고르기 - 138476'를 파이썬으로 풀어보았습니다.

문제에 대한 접근과정과 문제 풀이, 사용한 코드에 대한 지적 언제든 환영합니다.

 

프로그래머스, Programmers

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/138476?language=python3

프로그래머스

 

---

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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

---

문제 해결

귤의 크기별로 몇 개나 있는지 Counter를 이용해 구하고, 내림차순으로 정리했습니다.

그다음 빈도가 높은 귤의 크기부터 더해가며 몇 번 더해지는 지 계산하여 문제를 해결했습니다.

---

코드

def solution(k, tangerine):
    from collections import Counter
    
    size_cnt = Counter(tangerine)
    
    sorted_sizes = sorted(size_cnt.values(), reverse = True)
    
    total = 0
    cnt = 0
    
    for size in sorted_sizes:
        total += size
        cnt += 1
        
        if total >= k:
            return cnt

def solution(k, tangerine):
    from collections import Counter
    
    size_cnt = Counter(tangerine)
    
    sorted_sizes = sorted(size_cnt.values(), reverse = True)
    
    total = 0
    cnt = 0
    
    for size in sorted_sizes:
        total += size
        cnt += 1
        
        if total >= k:
            break;
            
    return cnt

반환을 언제 해주는 지에 따라 차이가 있나 싶어서 두개 모두 돌려봤습니다.

두 코드가 결과값을 언제 반환하느냐에만 차이가 있고, 실행 시간과 메모리를 사용하는 코드가 동일 하기에 시간복잡도와 메모리 사용은 동일하고, 직관성과 가독성에만 차이가 있다는 것을 알게 되었습니다.

---

사용한 개념

Counter()

'collections' 모듈에서 제공하는 클래스로 데이터에서 요소의 빈도를 계산할 때 사용합니다.

문제에서 사용한 것처럼 리스트나 문자열 등 반복 가능한 객체에서 각 요소가 몇 번 등장했는지 쉽게 계산할 수 있습니다.

https://docs.python.org/ko/3/library/collections.html#counter-objects

collections — Container datatypes

 

values()

딕셔너리 객체에서 사용되는 메서드로 딕셔너리의 모든 값들을 반환해줍니다.

'collections' 모듈의 'Counter' 역시도 딕셔너리와 유사한 인터페이스를 가지고 values()를 사용하면 각 요소의 빈도를 반환해줍니다.