99클럽 코테 스터디 19일차 TIL | 과일장수

🖥️ 문제

📝 풀이

import java.util.Arrays;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        
        // 사과 점수를 내림차순으로 정렬
        Arrays.sort(score);
        
        // 점수를 내림차순으로 변환 (높은 점수가 앞에 오도록)
        int n = score.length;
        int index = n - 1;
        
        // 상자에 담을 수 있는 사과의 개수
        while (index >= m - 1) {
            // 최저 점수
            int lowestScore = score[index - m + 1];
            // 이익
            answer += lowestScore * m;
            index -= m;
        }
        
        return answer;
    }
}

포인트는 정렬을 어떻게 진행하고, 이후에 최저점수를 최대화 해야한다는 것!
사실 정렬할 때 컬렉션으로 리버스 할까 하다가 속도가 너무 저하되어 약간의 꼼수로 와일문을 사용했다. for문을 사용할까 했지만 동적인 상황에선 while이 적당하다고 판단. 푸는데 1시간 정도 걸렸음.

👀 고찰

탐욕법(Greedy Algorithm)이란?
문제를 해결하는 데 있어 매 단계에서 가장 최적이라고 생각되는 선택을 하여 최종 해결책을 찾는 알고리즘으로 핵심은 현재 상황에서 최적의 선택을 하는 것! (ex. 동전 거스름돈 문제들)

탐욕법이라는 단어부터 조금 낯설어서 정확한 개념부터 잡고 들어갔다. 처음엔 문제조차 이해를 못했지만 회사에서 무지성으로 풀다보니 조금씩 알게 된 개념...