문제링크

문제 이해

[ 입력형태 / 조건 ]

k
사과의 최대 점수 | 3

m
한 상자에 들어가는 사과의 수 | 4

score
사과들의 점수 | [1, 2, 3, 1, 2, 3, 1]

[ 문제 ]

=> 과일 장수가 얻을 수 있는 최대 이익을 return

[ 풀이 ]

상자에 담을 사과의 개수는 고정이고, 가장 낮은 점수를 사과의 개수와 곱해서 구하는 것이므로, 가장 비싼 과일부터 담는 것이 이득임(그리디)
과일의 점수당 개수를 담은 배열을 선언하여, 마지막 인덱스부터 1씩 감소시키며 ans에 합산

---

코드

> [성공] 1차 시도 : int[] 이용

• 생각한 풀이 그대로 구현

class Solution {
    public int solution(int k, int m, int[] score) {
        int[] apple = new int[k+1];
        for(int sc : score){
            apple[sc]+=1;
        }
        
        int ans = 0, cnt = 0;
        for(int idx = k; idx > 0; idx--){
            cnt += apple[idx];
            if(cnt < m){
                continue;
            }
            ans += idx * m * (cnt/m);
            cnt %= m;
        }
        return ans;
    }
}

=> 빠르게 연산하기 위해 배열을 가져다 썼지만, 꽤나 느린 속도를 보였음

> [성공] 2차 시도 : Array.sort() 이용

• O(nlogn)이 되지만 가독성을 고려해 간단하게 바꿔봤음

import java.util.*;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;

        Arrays.sort(score);

        for(int i = score.length; i >= m; i -= m){
            answer += m * score[i - m];
        }
        return answer;
    }
}

=> 굉장히 오래 걸리는 연산이었음

TIP : 실제 실행결과로 오류가 있는지를 검증하지 말고, 여러 가능성을 생각해봐야 빠르게 오류를 막을 수 있다.