[프로그래머스] 귤 고르기(python)

문제

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

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

경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

 

 

제한조건

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

 

 입출력 예

 

 

 

 

풀이

 이 문제는 tangerine 배열을 보고 각각의 귤의 크기가 얼마인지를 보고난 후,  크기를 최대한 비슷하게 해야 하므로 같은 크기의 귤이 몇개인지를 카운트 해준 다음에 크기가 같은 귤이 많은 순서로 k 개의 귤을 담는 문제입니다. 

풀이하기 위해 먼저 tangerine 배열에서 각 숫자가 몇번 중복되는지를 알아낸 후, 최대한 적은 종류로 k 개를 담아 낼 수 있도록 중복되는 수를 담은 배열을 내림차순으로 정렬해서 몇 종류를 담으면 되는지 출력하면 됩니다.

 

1. set을 이용하여 귤의 크기가 몇 종류인지를 알아낸다.

2. tangerine 배열에서 각 종류의 귤이 몇개인지를 카운트 해주고, 카운트한 배열을 내림차순으로 정렬한다.

3. 그 후 배열의 0번째 값부터 더해주면서 k보다 크거나 같을 때 몇 종류의 귤이 담겼는지를 리턴해준다.

 

def solution(k, tangerine):
    tang = list(set(tangerine))
    temp = []
    result = 0
    answer = 0
    
    for i in tang:
        cnt = tangerine.count(i)
        temp.append(cnt)
        
    temp.sort(reverse=True)
    for i in temp:
        result += i
        answer += 1
        if(result >= k):
            return answer
        
    return answer

 

생각보다 문제가 쉽게 풀리는 느낌이 들어 테스트를 해보니 위와 같이 몇개의 테스트케이스에서 시간 초과로 실패하는 경우가 생겼습니다. 아마 중복요소를 제거하고, 또 tangerine 각 값을 모두 접근 후, 다시 정렬하는 과정까지 있어서 시간 초과가 되지 않았나 생각이 들었습니다.

 

그래서 다른 분들의 블로그를 참고 해보니 대부분의 블로그에서 Counter를 사용하여 배열의 중복 값을 찾고, most_common을 이용하여 최빈값 순서로 정렬 후, 몇 종류를 담았는지 찾는 방식으로 풀이를 진행한 경우가 많았습니다.

여러 블로그들을 참고하여 풀이를 진행한 코드는 아래와 같습니다.

 

1. Counter를 이용하여 같은 크기가 몇번 중복되었는지 확인한다.

2. most_common을 이용하여 최빈값 순서로 정렬한다.

3.그 후 value 값(temp[n][1]) 을 더해주면서 k보다 크거나 같을 때 몇 종류의 귤이 담겼는지를 리턴해준다.

from collections import Counter

def solution(k, tangerine):
    result = 0
    answer = 0
    
    temp = Counter(tangerine)
    temp = temp.most_common()
    
    for i in temp:
        result += i[1]
        answer += 1
        if(result >= k):
            return answer

 

 

위와 같이 풀이를 진행하니 모든 테스트 케이스를 통과하는 것을 확인할 수 있었습니다.