[Programmers] 이모티콘 할인행사 (JAVA)

프로그래머스

 

풀이

 

중복순열을 사용해서 문제를 해결하면 될 것 같았다.

혹시 시간초과가 발생할 까봐 계산해봤더니 모든 배열이 짧아서 가능할 것 같았다.

 

rate라는 할인율을 담은 배열을 만들어 tmp라는 중복순열을 만들어줬다.

이후 중복순열이 하나 완성되었을 때, 유저와 이모티콘 배열을 돌면서 금액을 계산해줬다.

모든 user를 전부 돌고난 뒤에는 PriorityQueue에 넣어 이모티콘 플러스를 가장 많이 신청한 경우를 출력해줬다.

 

전체코드

import java.io.*;
import java.util.*;

class Solution {
    static int rate[] = {10, 20, 30, 40};
    static boolean visited[] = new boolean[4];
    static List<int[]> list = new ArrayList<>();
    static int emoticons_cnt;
    static int tmp[];
    static PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<>(){
        public int compare(int[] o1, int[] o2){
            if(o1[0] > o2[0]){
                return -1;
            }else if(o1[0] < o2[0]){
                return 1;
            }else{
                if(o1[1] > o2[1]){
                    return -1;
                }else if(o1[1] < o2[1]){
                    return 1;
                }else{
                    return 0;
                }
            }
        }
    });
    public int[] solution(int[][] users, int[] emoticons) {
        emoticons_cnt = emoticons.length;
        tmp = new int[emoticons_cnt];
        Rate(0, users, emoticons);
        
        int[] answer = q.poll();
        return answer;
    }
    static void Rate(int c, int[][] users, int[] emoticons){
        if(c == emoticons_cnt){
            int plus = 0;
            int sum = 0;
            for(int i=0; i<users.length; i++){
                int each = 0;
                for(int j=0; j<emoticons.length; j++){
                    if(tmp[j] >= users[i][0]){
                        each += (emoticons[j]*(100-tmp[j])/100);
                    }else{
                        continue;
                    }
                }
                if(each >= users[i][1]){
                    plus++;
                }else{
                    sum += each;
                    each = 0;
                }
            }
            int case1[] = {plus, sum};
            q.offer(case1);
            return;
        }
        for(int i=0; i<4; i++){
            tmp[c] = rate[i];
            Rate(c+1, users, emoticons);
        }
    }
}