프로그래머스_귤 고르기_day12

 

알고리즘 챌린지 12일 차이다. 주말에 푹 쉬고 하니 확실히 상쾌하고 귀찮은 마음이 덜 생기는 것 같다. 목표를 향해 열심히 달려가는 것도 좋지만 역시 충분한 휴식이 병행되어야 한다는 점을 다시금 깨달았다. 

오늘은 프로그래머스 Level2로 분류된 귤고르기 문제이다. 

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

프로그래머스

 

해당 문제 또한 자료구조를 이용하면 쉽게 풀수 있는 문제로 최근에 풀었던 시소 짝꿍문제와 상당히 유사한 로직으로 풀이할 수 있다.

각 귤의 크기의 합이 주어진 k보다 크거나 같으면 되며, 서로 다른 귤의 무게가 최소의 조합으로 이루어지면 된다. 

자바에서는 Map.getOrDefault를, 파이썬에서는 Counter를 이용하여 각 무게의 빈도수를 구한 뒤, 빈도수를 기준으로 내림차순 정렬한다. 
종류가 많은 순서대로 변수에 누적합을 더해가면서 k와 값을 비교한다. 

상당히 간단한 로직으로 아래 코드를 보면 금방 이해가 될 것이다. 

Java

import java.util.*;
class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        int sum = 0;
        Map<Integer, Integer> counter = new HashMap<>();
        
        for(int a : tangerine) {counter.put(a, counter.getOrDefault(a, 0) + 1);}
        List<Integer> values = new ArrayList<>(counter.values());
        Collections.sort(values, Collections.reverseOrder());
        
        for(int num : values){
            if(sum + num >= k) {
                answer++;
                break;
            }else {
                sum += num; 
                answer++;
            }
        }
        return answer;
    }
}

Python

from collections import Counter
def solution(k, tangerine):
    answer = 0
    sum = 0
    
    counter = Counter(tangerine)
    sorted_guul = sorted(counter.items(), key=lambda x: x[1], reverse=True)
    
    for key, value in sorted_guul:
        if value + sum >= k:
            answer+=1
            break
        else:
            sum += value
            answer+=1
    return answer