150368. 이모티콘 할인행사

문제

https://school.programmers.co.kr/learn/courses/30/lessons/150368

제한사항

풀이

1. DFS를 사용하여 모든 할인율 조합 생성

2. 각 할인 조합에 대해 사용자 구매 시뮬레이션

3. 최적의 결과 저장

class Solution {
    static int maxSubscriberCount = 0;
    static int maxCost = 0;

    public int[] solution(int[][] users, int[] emoticons) {

        int[] answer = {};

        int[] discountRates = {10, 20, 30, 40};
        int[] discountCombination = new int[emoticons.length];

        dfs(0, users, emoticons, discountRates, discountCombination);

        answer = new int[]{maxSubscriberCount, maxCost};

        return answer;
    }

    void dfs(int depth, int[][] users, int[] emoticons, int[] discountRates, int[] discountCombination) {
        if(depth == emoticons.length) {

            evaluate(users, emoticons, discountCombination);

            return; 
        }

        for(int i=0;i<discountRates.length;i++) {
            discountCombination[depth] = discountRates[i];
            dfs(depth+1, users, emoticons, discountRates, discountCombination);
        }
    }

    void evaluate(int[][] users, int[] emoticons, int[] discountCombination) {

        int subscriberCount = 0;
        int totalCost = 0; 
        int m = emoticons.length;
        for(int[] user : users) {

            int userPurchaseCost = 0;
            for(int i=0;i<m;i++) {
                if(discountCombination[i]>=user[0]) {
                    userPurchaseCost += emoticons[i] * (100-discountCombination[i]) / 100;
                }
            }


            if(userPurchaseCost >= user[1]) {

                subscriberCount++;
            }   else {
                totalCost+= userPurchaseCost;
            }
        }

//         if(subscriberCount >= maxSubscriberCount) {
//             System.out.println("subscriberCount: " + subscriberCount);
//             System.out.println("totalCost: " + totalCost);

//             maxSubscriberCount = subscriberCount;
//             if(totalCost > maxCost)
//                 maxCost = totalCost;

//         }

        if (subscriberCount > maxSubscriberCount || 
           (subscriberCount == maxSubscriberCount && totalCost > maxCost)) {
            maxSubscriberCount = subscriberCount;
            maxCost = totalCost;
        }

    }
}

시간 복잡도 분석

• DFS 탐색: 4^m (최대 4^7 = 16,384 경우의 수)
• 각 경우의 수마다 O(nm) 연산:
  • 각 사용자가 모든 이모티콘을 확인해야 하므로 최악의 경우 100 * 7 = 700 연산
• 총 시간 복잡도: O(4^m * n * m)
  • m = 7, n = 100일 때 최악의 경우 약 1,638,400 연산으로 충분히 해결 가능

회고

1. DFS 탐색을 통해 모든 할인율 조합을 찾고 각 할인율을 적용해보는 문제였다. 문제를 풀 때마다 모든 경우를 다 찾아야 하는지 고민할 때가 많다. 그럴 때마다 시간 복잡도를 통해 판단해보자.

2. 아래 설명을 코드로 구현해보는데 생각하기 어려웠다. 다시 보면 좋을 것 같다.

if (subscriberCount > maxSubscriberCount || 
           (subscriberCount == maxSubscriberCount && totalCost > maxCost)) {
            maxSubscriberCount = subscriberCount;
            maxCost = totalCost;
        }