프로그래머스 이모티콘 할인행사

문제 풀이 방식

• 할인되는 모든 경우의 수(조합) 고려하기 -> 완전탐색으로 풀어야 하는거까진 알겠는데 구현을 어떻게 할지 모르겠음
• 참조한 풀이법 : https://rovictory.tistory.com/181

문제 풀이 (Java)

import java.util.*;


class Solution {
    List<int[]> list;
    int[] dis = {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) -> o1[0] == o2[0] ?  o2[1] - o1[1] : 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);
        }
    }
}