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

문제

https://www.acmicpc.net/problem/150368

풀이

• 할인 가능한 경우를 완전탐색하여, 각 할인 비율에 대해 금액을 구해서 가입 여부와 총 금액을 구한다.
• 가입 횟수와 금액 쌍을 우선순위 큐에 가입 횟수가 큰 순으로, 가입 횟수가 같다면 금액이 큰 순으로 넣는다.
• 모든 경우에 대해 계산이 끝나고 큐에서 가장 먼저 poll되는 것이 정답

유의할 점

• 완전탐색 코드를 작성하는데 바로 작성하지 못했다. 연습 필요

코드

import java.util.*; 

class Solution {    
    static PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->{
        if(o1[0]== o2[0]) return o2[1]- o1[1]; 
        else return o2[0]-o1[0];
    }); 
    public int[] solution(int[][] users, int[] emoticons) {
        double[] discount = new double[emoticons.length]; 
        dfs(0, discount,users,emoticons); 
        return pq.poll();
    }
    static void dfs(int length, double[] discount,int[][] users, int[] emoticons){
        if(length ==emoticons.length) {
            int registeration = 0; 
            double total=0; 
            for(int j=0; j<users.length; j++){
                int[] user =  users[j];
                double userDiscount = user[0]*1.0/100; 
                double money = user[1]; 
                double sum =0; 

                for(int i=0; i<emoticons.length; i++){
                    if(userDiscount<=discount[i]) {
                        sum+= (1-discount[i])* emoticons[i];
                    }
                }
                if(money<=sum) registeration++; 
                else total += sum; 
            }
            pq.add(new int[]{registeration, (int)total});
            return; 
        }
        for(int i=0; i<4; i++){
            discount[length]= (i+1)*1.0/10; 
        dfs(length+1, discount,users,emoticons); 
        }

    }
}