lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read




문제 풀이

이번 과일 장수 문제는 주어진 배열을 역순으로 그룹지어 접근하는 것이 핵심이다.
한 마디로 배열을 잘 다룰 줄 알아야 한다는 것이다.


아이디어 도출

처음엔 ArrayList를 활용하여 주어진 score 배열만큼 담은 다음 별도의 ArrayList에 add하고 remove하는 방식으로 접근하려 했으나 성능 이슈가 발생할 것 같아 그만두고 배열 자체를 잘 활용해보기로 하였다.

  • 주어진 score 배열을 오름차순으로 정렬한다.
    • 최대한 많은 이익을 내야 하기 때문에 오름차순으로 정렬하여 역순으로 큰 점수부터 접근하기 위함이다.
  • 몇 박스나 담을 수 있는지를 구한다.
    • score 배열의 길이에서 m을 나눈 값이 된다.
  • 박스 별로 [최소점수의 사과 * m]으로 최대 이익을 계산한다.
    • 배열을 역순으로 접근하는데, m만큼 박스로 구분지어 최소점수를 구하고 [최소점수 * m] 연산을 통해 박스 당 최대이익을 구할 수 있다.
  • 박스별로 구했던 최대이익을 모두 합한 값을 리턴한다.

이 때, 내가 푼 풀이과정에서는 k를 굳이 고려하지 않아도 정답을 내는데 상관이 없어 보인다.


이제 아이디어대로 코드를 구현해보자.

1
2
3
4
5

Arrays.sort(score);    
int answer = 0;
int idx = 0;
int bucketLength = score.length / m;
int[] buckets = new int[bucketLength];

먼저 입력으로 주어지는 score 배열을 오름차순으로 정렬한다.
모든 박스의 최대이익을 담을 answer 변수를 선언한다.
그리고 몇 박스나 담을 수 있는지를 구하여 박스당 이익을 담아둘 buckets 배열을 선언하고 초기화하자.

1
2
3
4
5
6
7
8

for(int i=score.length-1; i>=m-1; i-=m) {
    int min = 0;
    for(int j=i; j>i-m; j--) {
        min = Math.min(10, score[j]);
    }
    buckets[idx++] = min * m;
}
for(int bucket  : buckets) answer += bucket;

다음으로 score 배열을 거꾸로 역순으로 접근하는데 박스의 크기인 m만큼 나누어서 박스에 담아야 한다.

여기서 바깥쪽 for문에서는 i가 score.length-1부터 m-1이 될 때까지 m만큼 줄어들면서 반복하게 된다.
그리고 안쪽 for문에서는 j가 i부터 시작해서 i-m만큼, 즉 역순으로 m개 만큼 추가로 반복한다.

이 때, 박스에 담긴 사과의 점수들 중 최소점수를 구해야 하기 때문에 Math 클래스의 min 메소드를 활용해서 박스 별 최소점수를 구한다. 안쪽 for문이 종료되는 순간 하나의 박스에 대한 연산이 끝나고 최소점수가 min에 담겨지게 된다.

그리고 안쪽 for문이 종료되면 앞서 선언해둔 bucket 배열에 [최소점수 * m] 을 통해 박스별 최대이익 값을 담으면 된다.

Math.min(10, score[j])에서 10과 사과점수를 비교해 최소점수를 구하는 이유는 문제의 제한사항을 보면 사과의 점수 범위가 3 ≤ k ≤ 9 이기 때문이다.



작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.*;

class Solution {
    public int solution(int k, int m, int[] score) {
        Arrays.sort(score);    
        int answer = 0;
        int idx = 0;
        int bucketLength = score.length / m;
        int[] buckets = new int[bucketLength];
        
        for(int i=score.length-1; i>=m-1; i-=m) {
            int min = 0;
            for(int j=i; j>i-m; j--) {
                min = Math.min(10, score[j]);
            }
            buckets[idx++] = min * m;
        }

        for(int bucket  : buckets) answer += bucket;
        System.out.println(answer);
        return answer;
    }
}

회고

  • 배열을 역순으로 접근한다는 생각은 쉽게 할 수 있었지만, m을 활용하여 큰 점수부터 작은 점수까지 박스별로 묶어서 접근하는 방식을 생각해내기가 어려웠다.

You may also enjoy