[프로그래머스][정렬][JAVA] 과일 장수

문제 제목

https://school.programmers.co.kr/learn/courses/30/lessons/135808

프로그래머스

풀이 방법

쉽게 말해 일정 수만큼 집단을 나누는데 최솟값을 피해 큰 값부터 집단을 나누면 자연스레 최댓값이 도출되는 문제이다.배열을 정렬해서 큰 값부터 묶으면 해결된다.퀵 정렬 말고 다른 여러 정렬들에 대해서도 정리해놔야 할 것 같다.

소스 코드

class Solution {
    int[] score_global;
    
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        score_global = score;
        
        quickSort(0, score.length - 1);
        
        int cnt = 0;
        int min = 10;
        
        for(int i = score_global.length - 1; i >= 0; i--) {
            if(min > score_global[i])
                min = score_global[i];
            cnt++;
            
            if(cnt == m) {
                answer += min * cnt;
                cnt = 0;
                min = 10;
            }
        }
        
        return answer;
    }
    
    public void quickSort(int start, int end) {
        if(start >= end)
            return;
        
        int left = start;
        int right = end;
        int mid = (start + end) / 2;
        int pivot = score_global[mid];
        
        while(left <= right) {
            while(score_global[left] < pivot)
                left++;
            
            while(score_global[right] > pivot)
                right--;
            
            if(left <= right) {
                int tmp = score_global[left];
                score_global[left] = score_global[right];
                score_global[right] = tmp;
                
                left++;
                right--;
            }
        }
        
        if(start < right)
            quickSort(start, right);
        if(left < end)
            quickSort(left, end);
    }
}