[Leet Code] Maximum Units on a Truck

기면지·2021년 6월 14일

LeetCode

목록 보기

17/20

안녕하세요! 오늘은 6월 1주차 마지막 알고리즘인 Maximum Units on a Truck 풀이를 작성해 보겠습니다.

문제

요약
주어진 boxTypes 배열에서 i번째 배열의 0번째 인덱스 값은 box의 개수이고, 1번째 인덱스 값은 해당 box 안에 들어있는 unit 개수입니다. truckSize 넘지 않도록 box를 트럭에 실었을 때 최대 unit의 수를 return하는 문제입니다.

처음으로 생각한 방법

우선 boxTypes 배열을 정렬해야한다고 생각했습니다. 그래서 Arrays.sort() 를 사용해서 2차원 배열의 두번째 요소, 즉 unit 개수로 내림차순 정렬해서 진행했습니다.
그 후에는 while 문을 순회하면서 truckSize 를 box 개수로 다 채웠을 때 break 해주었습니다.

근데 위의 방법은 틀렸습니다..
while문의 조건을 잘못 해당했는지 arrayOutOfIndex 에러가 발생했습니다.

두번째로 생각한 방법

while문의 조건만 바꾸어주었습니다. 배열을 접근하는 index 변수가 배열 길이가 넘어가기 전까지만 순회하는 조건으로 변경했습니다.
결과는 Accept!

이제 코드 설명에 들어가겠습니다.

코드 설명

int result = 0;
int index = 0;

정답을 return할 result 변수와 boxTypes 배열의 index를 접근할 index 변수를 함수 내부에 선언해주었습니다.

Arrays.sort(boxTypes, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        if (o1[1] == o2[1]) {
            return o2[0] - o1[0];
        } else {
            return o2[1] - o1[1];
        }
    }
});

위에서 말했던 boxTypes 배열을 정렬하는 코드입니다.
Arrays.sort 를 단순하게 사용하는 것이 아닌 Comparator 를 적용해주었습니다.
만약, 2차원 배열의 unit 개수가 동일하다면 box를 갖고 있는 수로 내림차순을 진행합니다.
unit 개수가 동일하지 않다면 unit이 많은 것부터 내림차순 정렬합니다.

while (index < boxTypes.length) {
    if (truckSize - boxTypes[index][0] < 0) {
        result += boxTypes[index][1] * truckSize;
        break;
    } else {
        result += boxTypes[index][1] * boxTypes[index][0];
        truckSize -= boxTypes[index][0];
        index++;
    }
}

while문의 조건은 위에서 설명한 것과 동일하게 index 변수가 배열의 길이를 넘어가지 않을 때만 순회합니다.
이것은 truckSize 를 다 채우지 못하는 경우도 있기 때문입니다.

그 후 2차원 배열의 box 개수가 남아있는 truckSize 보다 크다면 result 변수에 unit을 truckSize 만큼 곱해서 더해줍니다.
그 후 truckSize 를 모두 사용했기 때문에 while문을 빠져나오는 break를 걸어줍니다.

만약 위의 경우가 아니라면 result 변수에 unit을 box 개수만큼 곱한 값을 더해줍니다.
truckSize 를 방금 result 에 더해준 box 개수만큼 빼서 다시 저장합니다.
마지막으로 index 값을 하나 추가하고 반복문을 순회합니다.

전체 코드

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        int result = 0;
        int index = 0;

        Arrays.sort(boxTypes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o2[0] - o1[0];
                } else {
                    return o2[1] - o1[1];
                }
            }
        });

        while (index < boxTypes.length) {
            if (truckSize - boxTypes[index][0] < 0) {
                result += boxTypes[index][1] * truckSize;
                break;
            } else {
                result += boxTypes[index][1] * boxTypes[index][0];
                truckSize -= boxTypes[index][0];
                index++;
            }
        }

        return result;
    }
}