(Java) 프로그래머스 - 이모티콘 할인행사

문제를 읽고 대략적인 로직은 빠르게 세워졌지만 구현에는 꽤 많은 시간이 소요되었다.

인풋 값이 크지 않아서 시간 초과는 생각하지 않고 풀었다.

먼저 가능한 할인 조합을 만들고 users 배열과 emoticons 배열을 순회하며 계산후

result 배열에 담고 정렬해주었다.

총 1시간 정도 걸렸는데 풀이 시간을 더 빠르게 하고 싶다...

 

---

 

최종 코드

import java.util.*;
class Solution {
    static List<int[]> list;
    static int[] dis = new int[] {10,20,30,40};
    public int[] solution(int[][] users, int[] emoticons) {

        int[] answer = new int[2];
        list = new ArrayList<>();
        List<int[]> result = new ArrayList<>();
        com(0, emoticons.length, 0, new int[emoticons.length]);

        int cnt = 0;
        while (cnt < list.size()) {
            int userPlus = 0;
            int userSum = 0;

            for (int i = 0; i < users.length; i++) {
                int sum = 0;
                int[] discount = list.get(cnt);
                for (int j = 0; j < emoticons.length; j++) {
                    if (users[i][0] <= discount[j]) {
                        sum += emoticons[j] - emoticons[j] * discount[j] / 100;
                    }
                }
                if (sum >= users[i][1]) {
                    userPlus++;
                    sum = 0;
                }
                userSum += sum;
            }

            cnt++;
            result.add(new int[]{userPlus, userSum});
        }

        result.sort((o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o2[1] - o1[1];
            } else {
                return o2[0] - o1[0];
            }
        });


        answer = result.get(0);

        return answer;
    }
    
    public void com(int idx, int size, int depth, int[] arr) {
        if (size == depth) {
            int[] temp = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                temp[i] = arr[i];
            }
            list.add(temp);
            return;
        }

        for (int i = 0; i < 4; i++) {
            arr[idx] = dis[i];
            com(idx + 1, size, depth + 1, arr);
        }
    }
}