[프로그래머스/Java] 이모티콘 할인행사

https://school.programmers.co.kr/learn/courses/30/lessons/150368

프로그래머스

 

할인율을 적용할때, Dfs을 이용하여 풀 수 있습니다.

또한 Comparable을  이용해 리턴할 리스트의 1번째값들이 정답이 되도록 정렬하였습니다. 

import java.util.*;
class Solution {
            static class Service implements Comparable<Service>{
                int num;
                int price;

                public Service(int num, int price) {
                    this.num = num;
                    this.price = price;
                }

                public int getNum() {
                    return num;
                }

                public void setNum(int num) {
                    this.num = num;
                }

                public int getPrice() {
                    return price;
                }

                public void setPrice(int price) {
                    this.price = price;
                }

                @Override
                public int compareTo(Service o){
                    return this.num==o.num ? this.price-o.price : this.num-o.num;
                }
            }
            public  static int[] solution(int[][] users, int[] emoticons){
                int[] rate= {10,20,30,40};
                int[] arr= new int[emoticons.length];
                List<Service> serviceList= new ArrayList<>();
                dfs(rate,emoticons,arr,users,serviceList,0);

                serviceList.sort(Comparator.reverseOrder());
                return new int[]{serviceList.get(0).getNum(),serviceList.get(0).getPrice()};
            }

            private static void dfs(int[] rate, int[] emoticons, int[] arr, int[][] users, List<Service> serviceList, int depth) {
                if (depth==emoticons.length)
                {
                    int price=0;
                    int num=0;
                    for (int[] user : users) {
                        int r=user[0];
                        int th=user[1];
                        int sum=0;
                        for (int i=0;i< arr.length;i++){
                            if(arr[i]>=r){
                                sum+=emoticons[i]*(1-((double)arr[i])/100);
                            }
                        }
                        if(sum>=th){
                            num++;
                        }else {
                            price+=sum;
                        }
                    }
                    serviceList.add(new Service(num,price));
                    return;
                }
                for (int i : rate) {
                    arr[depth]=i;
                    dfs(rate,emoticons,arr,users,serviceList,depth+1);
                }
            }

        }