이모티콘 할인행사(PG_LV2_150368)

1. 문제 링크

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

프로그래머스

---

 

2. 나의 코드

메모리: 70MB
시간: 0.04ms 
시간 복잡도 : O(4^N)
설명
- 각 이모티콘의 할인율을 부분집합을 사용
- 부분집합으로 만들 수 있는 모든 경우의 수를 계산

class Solution {
    static int[] input;
    static int maxSubscriber, maxAmount;
    
    public int[] solution(int[][] users, int[] emoticons) {
        input = new int[emoticons.length];
        subset(0, users, emoticons);
        int[] answer = {maxSubscriber, maxAmount};
        return answer;
    }
    
    public static void subset(int cnt, int[][] users, int[] emoticons) {
        if (cnt == emoticons.length) {
            int subscriber = 0;
            int amount = 0;
            for (int[] user : users) {
                int sum = 0;
                for (int i = 0; i < emoticons.length; i++) {
                    if (user[0] <= input[i]) {
                        sum += emoticons[i] * ((100 - input[i]) * 0.01);
                    }
                }
                if (sum >= user[1]) {
                    subscriber++;
                } else {
                    amount += sum;
                }
            }
            if (maxSubscriber < subscriber) {
                maxSubscriber = subscriber;
                maxAmount = amount;
            }  else if (maxSubscriber == subscriber && maxAmount < amount) {
                maxSubscriber = subscriber;
                maxAmount = amount;
            }
            return;
        }

        input[cnt] = 10;
        subset(cnt + 1, users, emoticons);
        input[cnt] = 20;
        subset(cnt + 1, users, emoticons);
        input[cnt] = 30;
        subset(cnt + 1, users, emoticons);
        input[cnt] = 40;
        subset(cnt + 1, users, emoticons);
    }
}

 

---

 

3. 정답 코드

class Solution {
   
    static int userCnt, emoticonCnt, plusMemberMaxCnt, salesMaxAmount;
    static int[] discounts, emoticons;
    static int[][] users;
    
    public int[] solution(int[][] users, int[] emoticons) {
        userCnt = users.length;
        emoticonCnt = emoticons.length;
        discounts = new int[emoticonCnt];
        this.users = users;
        this.emoticons = emoticons;
        
        recur(0);
        
        int[] answer = new int[2];
        answer[0] = plusMemberMaxCnt;
        answer[1] = salesMaxAmount;
        return answer;
    }
    
    // 이모티콘 할인 경우의 수 찾기
    private void recur(int cnt) {
        if (cnt == emoticonCnt) {
            calculate();
            return;
        }
        
        for (int i = 10; i <= 40; i += 10) {
            discounts[cnt] = i;
            recur(cnt + 1);
        }
    }
    
    private void calculate() {
        int plusMemberCnt = 0;
        int salesAmount = 0;
        
        for (int i = 0; i < userCnt; i++) {
            int userRatio = users[i][0];
            int userPrice = users[i][1];
            int totalPrice = 0;
            boolean flag = false;
            
            for (int j = 0; j < emoticonCnt; j++) {
                int discount = discounts[j];
                int price = emoticons[j];
                if (discount >= userRatio) {
                    totalPrice += emoticons[j] / 100 * (100 - discount);
                }
                if (totalPrice >= userPrice) {
                    flag = true;
                    break;
                }
            }
            
            if (flag) {
                plusMemberCnt++;
            } else {
                salesAmount += totalPrice;
            }
        }
        
        if (plusMemberMaxCnt < plusMemberCnt) {
            plusMemberMaxCnt = plusMemberCnt;
            salesMaxAmount = salesAmount;
        } else if (plusMemberMaxCnt == plusMemberCnt) {
            salesMaxAmount = Math.max(salesMaxAmount, salesAmount);
        }
    }
}

 

---

 

4. 배운 점

- 부분집합, 순열, 조합은 항상 다시 보자!