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

🎨 문제

프로그래머스

📘 풀이

이 문제는 완전 탐색으로 해결할 수 있습니다. 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다. 각 이모티콘의 할인율을 정하고 이에 따라 이모티콘 플러스 가입자 수와 총판매액을 구할 수 있습니다. 따라서 가능한 할인율을 모두 구하고 이 둘이 최대인 값을 구하면 됩니다.

 

 

DFS, 백트래킹으로 가능한 할인율 순열을 구합니다.

 

private static final int[] RATE = {90, 80, 70, 60};

private void dfs(int[] emoticons, int[][] users, int cur, int[] rates) {
    if (cur == emoticons.length) {
        updateAnswer(emoticons, users, rates);
        return;
    }

    for (int rate : RATE) {
        rates[cur] = rate;
        dfs(emoticons, users, cur + 1, rates);
    }
}

 

할인율 순열을 가지고 각 유저가 이모티콘 플러스를 가입할지 아니라면 판매액은 얼마인지 계산합니다. 계산된 결과로 정답 배열을 업데이트합니다.

 

private static int EMOTICON_PLUS = 0;
private static int TOTAL_SALES = 0;

private void updateAnswer(int[] emoticons, int[][] users, int[] rates) {

    int ePlus = 0;
    int totalExpense = 0;

    for (int[] user : users) {
        int expense = 0;
        int rate = user[0];
        int price = user[1];
        for (int i = 0; i < rates.length; i++) {
            if (100 - rates[i] >= rate) {
                expense += emoticons[i] * rates[i] / 100;
            }
            if (expense >= price) {
                ePlus += 1;
                expense = 0;
                break;
            }
        }
        totalExpense += expense;
    }

    if (ePlus > EMOTICON_PLUS) {
        EMOTICON_PLUS = ePlus;
        TOTAL_SALES = totalExpense;
    } else if (ePlus == EMOTICON_PLUS) {
        TOTAL_SALES = Math.max(totalExpense, TOTAL_SALES);
    }
}

📗 코드

import java.util.Arrays;

class Solution {

    private static final int[] RATE = {90, 80, 70, 60};
    private static int EMOTICON_PLUS = 0;
    private static int TOTAL_SALES = 0;

    public int[] solution(int[][] users, int[] emoticons) {
        getPrices(emoticons, users, 0, new int[emoticons.length]);
        return new int[]{EMOTICON_PLUS, TOTAL_SALES};
    }

    private void getPrices(int[] emoticons, int[][] users, int cur, int[] rates) {
        if (cur == emoticons.length) {
            updateAnswer(emoticons, users, rates);
            return;
        }

        for (int rate : RATE) {
            rates[cur] = rate;
            getPrices(emoticons, users, cur + 1, rates);
        }
    }

    private void updateAnswer(int[] emoticons, int[][] users, int[] rates) {

        int ePlus = 0;
        int totalExpense = 0;

        for (int[] user : users) {
            int expense = 0;
            int rate = user[0];
            int price = user[1];
            for (int i = 0; i < rates.length; i++) {
                if (100 - rates[i] >= rate) {
                    expense += emoticons[i] * rates[i] / 100;
                }
                if (expense >= price) {
                    ePlus += 1;
                    expense = 0;
                    break;
                }
            }
            totalExpense += expense;
        }

        if (ePlus > EMOTICON_PLUS) {
            EMOTICON_PLUS = ePlus;
            TOTAL_SALES = totalExpense;
        } else if (ePlus == EMOTICON_PLUS) {
            TOTAL_SALES = Math.max(totalExpense, TOTAL_SALES);
        }
    }


}