[프로그래머스] 과일 장수 문제 - Java

프로그래머스 스쿨의 Lv1 과일 장수 문제를 아래와 같이 풀었는데 시간초과가 떴다.

class Solution {
    public int solution(int k, int m, int[] score) {

        int answer = 0;

        List<Integer> intList = Arrays.stream(score)
                .boxed()
                .collect(Collectors.toList());

        Collections.sort(intList, Collections.reverseOrder());

        Stack<Object> stack = new Stack<>();
        for (int i = 0; i < score.length - (score.length % m); i++) {
            stack.push(intList.remove(0));
            if (stack.size() == m) {
                answer += (m * Integer.parseInt(stack.peek().toString()));
                stack.clear();
            }
        }

        return answer;
    }
}

 

내가 생각한 로직은 아래와 같다.

1. int형 배열을 List로 변환 후, 내림차순 정렬해준다.

 

2. 내림차순 정렬해준 List를 첫번째 index부터 (리스트 길이 - 리스트 길이에서 m값을 나눈 나머지)까지 반복문을 돌면서 차례대로 stack에 push한다.

 

3. stack의 size가 m이 되면, stack에서 제일 마지막에 넣은 값(내림차순 정렬 했기에 최소값이 됨)을 가져와서 m과 곱해서 answer에 더해준다.

 

4. stack을 clear하고 계속 반복한다. 

---

왜 시간초과가 떴을까 생각을 해보았는데,

int형 배열에서 Integer형 리스트로 변환하는 과정에서 시간을 많이 사용한 것 같고,

굳이 stack을 사용안해도 될 문제였고, 리스트 길이 만큼 전체 반복을 안해도 될 문제인데 해서 시간초과가 뜬 것 같다.

---

그래서 내가 다시 생각한 로직은 아래와 같다.

 

1. 배열 오름차순 정렬

 

2. 오름차순 정렬 했기 때문에,  배열의 길이를 m으로 나눈 나머지를 i의 시작값으로 설정한다

=> 예를 들어, m은 4이고, [1, 2, 3, 1, 2, 3, 1]배열을 오름차순 하면 [1, 1, 1, 2, 2, 3, 3]이 되는데 [2, 2, 3, 3]일때가 최소값이 가장 크므로, 배열의 길이(=7)을 m(=4)으로 나눈 나머지는 3이고 그만큼 버려야 한다. 따라서 시작점을 나머지의 인덱스로 설정하는것이다.

 

3. 그리고 반복문이 돌면서 더해지는 i의 값은 +1이 아닌, m만큼 더해준다.

=> 인덱스를 다 탐색할 필요없이, 오름차순 정렬이기에 최소값만 구해주면 되기때문

 

4. 반복문을 돌면서 해당 배열의 인덱스 값 * m을 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 % m; i < score.length; i= i+m) {
            answer += score[i]*m;
        }
         return answer;
    }
}

 

훨씬 간단한 문제였다.