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

문제링크

문제 접근

• 이모티콘 별 할인율 중복순열로 생성
• 최대 경우의 수 4^7(할인율 4개,이모티콘 최대7개) * 100(유저 100명)
• 할인율 생성되는 경우마다 이모티콘 플러스 가입자, 판매액 계산하여 최선의 경우 찾기

코드

class Solution {
    static int[] discount = {10,20,30,40};
    static int m,n,max1,max2;
    static int[] result;
    static int[][] user;
    static int[] emoticon;
    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = new int[2];
        user = users;
        emoticon = emoticons;
        m = emoticons.length;
        n = users.length;
        result = new int[m];
        perm(0);
        answer[0] = max1;
        answer[1] = max2;
        return answer;
    }
    public void perm(int idx){ //이모티콘 별 할인율 중복순열 생성
        if(idx == m){ //이모티콘 할인율 경우의수 생성 완료
            check();
            return;
        }
        for(int i=0;i<4;i++){
            result[idx] = discount[i];
            perm(idx+1);
        }
    }
    public void check(){
        int num1 = 0;
        int num2 = 0;
        for(int i=0;i<n;i++){
            int dc = user[i][0];
            int buy = 0;
            for(int j=0;j<m;j++){
                if(dc <= result[j]){
                    buy += emoticon[j] * (100-result[j]) / 100;
                }
            }
            if(buy >= user[i][1]) num1++;
            else num2 += buy;
        }
        if(max1 < num1){
            max1 = num1;
            max2 = num2;
        }
        else if(max1 == num1){
            max2 = Math.max(max2, num2);
        }
    }
}

결과

정리

• 완전탐색 순조부 가능한지 시간체크 후 진행