[프로그래머스] 이모티콘 할인행사 자바 (Level 2) DFS

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/150368

1. 문제 요약

• 이모티콘 플러스 가입자수를 늘리고 이모티콘 판매액을 최대한으로 달성할 수 있는
• 이모티콘별 최적의 할인율을 구하여 산출된 [이모티콘 플러스 가입자수, 이모티콘 판매액]을 구하시오.
• 할인율은 10%단위로 10% ~ 40% 까지 적용할 수 있음

2. 핵심 아이디어

• DFS로 할인율 조합 4ⁿ개 생성 (n: 이모티콘 개수)
• 각 조합마다 사용자 반응을 시뮬레이션
• 가입자 수, 판매액 기준으로 최적 결과 저장

3. 풀이 코드

/**
     * 할인률 : 10~ 40% (단위:10 %)
     * @param users [구매기준%, 가격기준]
     * @param emoticons [이모티콘별 가격]
     * @return [이모티콘 플러스 가입자수, 이모티콘 판매액]
     */
    //사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입
    /*
    이벤트 목표
    1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
    2. 이모티콘 판매액을 최대한 늘리는 것.

    자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매
    자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입

     */
    int[][] users;
    int[] emoticons;
    int maxPlus = 0;
    int maxRevenue = 0;

    public int[] solution(int[][] users, int[] emoticons) {
        this.users = users;
        this.emoticons = emoticons;

        // 이모티콘 수만큼의 할인율 조합 배열
        int[] discounts = new int[emoticons.length];
        dfs(0, discounts);

        return new int[]{maxPlus, maxRevenue};
    }

    // 할인율 조합 생성
    private void dfs(int depth, int[] discounts) {
        if (depth == emoticons.length) {
            simulate(discounts);
            return;
        }

        for (int rate : new int[]{10, 20, 30, 40}) {
            discounts[depth] = rate;
            dfs(depth + 1, discounts);
        }
    }

    // 현재 할인율 조합에 따라 사용자 반응 시뮬레이션
    private void simulate(int[] discounts) {
        int plusCount = 0;
        int revenue = 0;

        for (int[] user : users) {
            int minDiscount = user[0];
            int maxPay = user[1];

            int total = 0;
            for (int i = 0; i < emoticons.length; i++) {
                if (discounts[i] >= minDiscount) {
                    int discountedPrice = emoticons[i] * (100 - discounts[i]) / 100;
                    total += discountedPrice;
                }
            }

            if (total >= maxPay) {
                plusCount++;
            } else {
                revenue += total;
            }
        }

        if (plusCount > maxPlus || (plusCount == maxPlus && revenue > maxRevenue)) {
            maxPlus = plusCount;
            maxRevenue = revenue;
        }
    }

4. 회고 및 느낀점

• 입력받은 파라미터를 전역변수로도 저장하고 활용할 수 있다는 것을 알았다.
• 작업을 세분화하면 로직을 짜는데 더 수월할 수 있다. ( 조합 만들기 dfs , 조합 시도 simulate )