Reducing Dishes(1402, leetcode)

문제 설명

셰프는 각 음식 별 만족도 배열을 가지고 있다. 시간 1마다 하나의 음식을 만들수 있다고 했을 때, 총 만족도는 시간[i] * 만족도[i]의 총 합이다. 총 만족도를 구할 때는 음식의 순서가 변할 수 있고 원한다면 음식을 뺄 수도 있다. 가장 큰 총 만족도를 구하시오.

사실 문제가 어렵다기보다 문제를 잘 이해해야 하는 문제였다.

처음 문제를 봤을 때는 예시 1만 보고 5*3은 15니까 15가 답 아닌가? 싶었다.

(-11 + 02 + 53 = 14)를 해줄 바에야 그냥 53만 해주면 최대 값이니까. 그러나 여기서 중요한 점이 있다. 음식이 걸리는 시간은 해당 음식이 만들어질 때까지 걸린 시간에서 1을 더한 값을 곱하는 거라고. 즉, 5만을 조리한다고 치면 5*1이라 답이 되지 않는 것이다.

문제 풀이

첫 번째 접근(내 풀이 + 다른 사람 풀이)

일단 만족도를 기준으로 배열을 정렬했다. 혹시 몰라서 인덱스를 같이 넣은 클래스 pair을 생성했지만, 음식의 순서는 원하는 대로 바꿀 수 있기에 이건 그다지 필요한 값은 아니었다.

그리고 정렬된 배열을 뒤에서부터 반복문을 돌리는데(오름차순 정렬이라) 여기서 tmp에 새로운 만족도를 더해준다. 만일 tmp가 음수가 나오면 뒤의 answer가 -가 되니까 continue를 한다. 만일 tmp가 양수라면 구한 tmp 값을 answer에다가 더해주면 된다.

이렇게 되면 tmp가 0이 되지 않을 때까지 값이 중첩되서 더해진다.

코드

Java

import java.util.*;

class pair implements Comparable<pair>{
    int s;
    int index;

    pair(int s, int inedx){
        this.s = s;
        this.index = index;
    }
    
    @Override
    public int compareTo(pair o1){
        return this.s - o1.s;
    }
}

class Solution {
    public int maxSatisfaction(int[] satisfaction) {

        List<pair> new_satisfaction = new ArrayList<>();
        
        //pair[] new_satisfaction = new pair[satisfaction.length];

        for(int i=0; i<satisfaction.length; i++){
            new_satisfaction.add(new pair(satisfaction[i], i+1));
        }

        Collections.sort(new_satisfaction);

        int tmp = 0;
        int answer = 0;

        for(int i=satisfaction.length - 1; i >= 0; i--){

            tmp += new_satisfaction.get(i).s;

            System.out.print(tmp + ": ");

            if(tmp < 0){
                continue;
            }

            answer += tmp;

            System.out.print(answer + " ");

        }

        return answer;
    }
}

링크

https://leetcode.com/problems/reducing-dishes/description/