프로그래머스 | 과일 장수 (Java)

🔒 문제

프로그래머스 Lv.1 과일 장수

🔑 해결

사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 작성하는 문제이다.

🔐 시도

[1차 시도] LinkedList를 사용 -> 시간 초과 발생.
1. 내림차순으로 정렬
2. 각 상자의 최소 점수를 LinkedList에 넣기
3. 이익 계산
을 시도했지만 시간 초과였다.

import java.util.LinkedList;
class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        
        // 정렬
        for (int i = 0; i < score.length; i++) {
			for (int j = score.length-1; j > i; j--) {
				if (score[i] < score[j]) {
					int tmp = score[i];
					score[i] = score[j];
					score[j] = tmp;
				}
			}
		}
        
        // 각 상자의 최소 점수
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < score.length; i++) {
			if ( (i+1) % m == 0) {
				list.add(score[i]);
			}
		}
        
        // 이익 계산
        for (Integer cost : list) {
			answer += cost * m;
		}
        
        return answer;
    }
}

[2차 시도] 최소 점수와 이익 계산을 while문으로 합침 -> 시간 초과 발생
1. 정렬 코드는 수정하지 않은 채로,
2. 최소 점수와 이익 계산 코드 수정.
했지만 시간 초과 발생. 여기서 정렬 부분이 시간 초과의 원인일 것이라 판단.

...
// 각 상자의 최소 점수와 이익계산
        int n = m-1;
        while(n < score.length) {
        	answer += score[n] * m;
        	n += m;
        }

🔓 코드

Arrays의 sort 함수를 사용하여 오름차순으로 정렬.
앞에서 부터 m번째인 값(한 상자에 들어있는 최저 점수)를 찾아 이익 계산.

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- m;
        while(n >= 0) {
        	answer += score[n] * m;
        	n = n - m;
        }
        
        return answer;
    }
}