[PGM] Level.2 귤 고르기

 

코딩테스트 연습 - 귤 고르기

문제설명
귤 크기를 분류했을 때 서로 다른 종류의 수를 최소화

ex. 총 8개의 귤, 6개만 판매할 때 크기 종류가 가작 적게 판매

귤 사이즈  [1,2,2,3,3,4,5,5] => [2,2,3,3,5,5] => 3가지 종류

 

접근방법

그리디 활용

1. 딕셔너리 key 귤크기, value 갯수
2. 갯수 많은 것부터 판매(0,음수가 되면 종료)

 

구현코드

[Python]

import collections
def solution(k, tangerine):
    type_count=0
    counter_dict = collections.Counter(tangerine)
    #print(counter_dict)
    
    for count in sorted(counter_dict.values(),reverse=True):
        k-= count # 많이 나온 귤부터 빼기
        type_count+=1 # 종류 1개 증가
        if k<=0: #음수면 멈춤
            break
        
    return type_count

 

[Java]

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {   
        
        int typeCount = 0;
        
         // 1. 귤 크기별 개수 세기
        HashMap<Integer,Integer> countMap =new HashMap<>();
        for (int size : tangerine) {
            countMap.put(size, countMap.getOrDefault(size, 0) + 1);
        }
        
        // 2. 개수별 내림차순 정렬 리스트
        List<Integer> countList = new ArrayList<>(countMap.values());
        countList.sort(Collections.reverseOrder());
        
        // 3. 갯수 많은 것부터 선택(k<1 종료)
        for(int count:countList){
            k -=count;
            typeCount++;
            if(k<=0){
                break;
            }
        }

        return typeCount;
    }
}

▶Stream 정렬 활용

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        HashMap<Integer,Integer> map =new HashMap<>();
		//귤 <사이즈,갯수>
        for (int t : tangerine) {
            map.put(t, map.getOrDefault(t, 0) + 1);
        }
		//귤 크기 리스트
        List<Integer> list = new ArrayList<>(map.keySet());
        //귤 크기를 갯수 기준으로 내림차순 정렬
        list.sort((o1, o2) -> map.get(o2)-map.get(o1));
		//갯수 많은 것부터 고르기
        for(Integer key:list){
            k-=map.get(key);
            answer++;
            if(k<=0){
                break;
            }
        }

        return answer;
    }
}