귤 고르기

• 문제 설명
  • 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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
• 입출력 예

• 오류코드
  • 문제에서 1,4인 귤을 제외 한다고 하여 고정으로 1과 4를 제외하도록 코드를 작성
  • 딕셔너리를 이용하여 귤들의 갯수를 카운트
  • 이후 갯수를 k만큼 담는데 그 종류를 answer에 저장하여 몇 가지의 귤이 담기는 확인
  • 문제에 나와있는 데로 리턴은 하나 제출시 17점이라는 낮은 점수를 받게 되었음
  • 질문하기 쪽 확인하니 1,4인 귤을 고정으로 제거 하는게 아닌 낮은 수를 제외하는 방식임을 확인
  • 이후 수정 후 제출 하였으나 똑같이 17점이라는 낮은 점수를 받게 됨

#1차
def solution(k, tangerine):
    answer = 0
    dict_t = {}
    for i in tangerine:
        if i == 1 or i == 4 : continue
        if i in dict_t:
            dict_t[i] += 1
        else:
            dict_t[i] = 1
    
    for name,value in dict_t.items():
        k = k - value
        answer += 1        
        if k <= 0: break
        
    
    return answer

#2차
def solution(k, tangerine):
    answer = 0
    dict_t = {}
    for i in tangerine:
        if i not in dict_t: dict_t[i] = 1
        else: dict_t[i] += 1
    
    for name,value in dict_t.items():
        if value < 2 : continue
        k = k - value
        answer += 1        
        if k <= 0: break
    return answer

 

• 수정코드
  • 방식을 수정하여 내림차순으로 정렬하여 큰 수부터 k만큼 제외 하고 그 가짓수를 answer에 저장하게 수정
  • 이후 정상적으로 통과됨을 확인

def solution(k, tangerine):
    answer = 0
    dict_t = {}
    for i in tangerine:
        if i not in dict_t: dict_t[i] = 1
        else: dict_t[i] += 1
    
    check=sorted(dict_t.values(),reverse=True)

    for value in check:
        k = k - value
        answer += 1        
        if k <= 0: break
        
    return answer

 

• 결론
  • 해당 문제는 귤의 크기를 먼저 나누고 크기에 맞게 귤을 센 후 많은 귤을 먼저 빼는 방식으로 해야지만 해당 문제를 해결 할 수 있음
  • 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하는 문제라서 귤의 갯수가 많은거 부터 빼야지만 최소값을 구할 수 있고 반대로 다른 종류의 수가 최대 값을 return 하게 하는 문제 였다면 정렬을 오름차순 정령 후 그 것부터 빼는 방식으로 하면 최대값을 구 할 수 있음