Lv.1 : 과일 장수

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 입력된 점수의 사과들로 한 상자에 m개씩 담았을때 최대 이익을 구한다.
• 2가지 풀이를 생각했다.
  1. 사과 점수를 정렬후 인덱스를 m개씩 이동해서 누적한다.
  2. 사과 점수를 배열에 카운트 후 m개씩 카운트해서 누적한다.
• 사과 점수의 길이가 100만까지 가기 때문에 터지진 않지만, 정렬에서 시간 복잡도가 더 커질 것 같아 2번을 선택했다.

🔸 코드 🔸

import java.util.Arrays;

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

        int[] points = new int[k+1];
        for(int i : score) 
            points[i]++;

        int count = 0;
        while(k > 0) {
            if(points[k] > 0){
                points[k]--;
                if(++count == m) {
                    count = 0;
                    answer += k*m;
                }
            }else {
                k--;
            }
        }

        return answer;
    }
}   

// import java.util.Arrays;

// 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 += score[i - m] * m;
//         }

//         return answer;
//     }
// }

🔸 코드 해석 🔸

• score 배열에서 각 점수를 points 배열의 인덱스로 카운트해 저장한다.
• points 배열의 마지막 인덱스부터 1까지 m개씩 카운트하며 answer에 누적한다.
• 아래 주석은 sort코드이다.

---

🔸 end 🔸

• sort풀이가 코드는 더 짧고 간단하지만, 시간 복잡도가 커지는 걸 알 수 있다.

왼쪽이 위 코드, 오른쪽이 정렬 풀이 결과