[2023 KAKAO BLIND RECRUITMENT] 이모티콘 할인행사

[2023 KAKAO BLIND RECRUITMENT] 이모티콘 할인행사

🙋‍♂️ 들어가며

이번 문제는 최악의 연산횟수가 다음과 같겠다

$4^7$

만약 이모티콘의 길이라 2라면 아래처럼 총 64번을 탐색하겠군.

그리고 1순위가 멤버쉽,

2순위는 이모티콘 구매이므로

멤버쉽이 같을때는 구매값이 클때 갱신이 필요하겠군

✅ 코드

class Solution {
    static int m;
    static int[] discount_rate = {10, 20, 30, 40};
    static int[] answer;
    static int max_membership;
    static int max_price_sum;
    
    public int[] solution(int[][] users, int[] emoticons) {
        answer = new int[2];
        
        m = emoticons.length;
        
        max_membership = 0;
        max_price_sum = 0;
        
        int[] selected_discount_rate = new int[m];
        back_tracking(0, selected_discount_rate, users, emoticons);
        
        answer[0] = max_membership;
        answer[1] = max_price_sum;
        return answer;
    }
    
    
    
    static void back_tracking(int idx, int[] selected_discount_rate, int[][] users, int[] emoticons) {
        // 끝지점 도달시
        if (idx == m) {
            caclulate(users, selected_discount_rate, emoticons);
            return;
        }
        
        // 아직 아니라면
        for (int i = 0; i < 4; i++) {
            selected_discount_rate[idx] = discount_rate[i];
            back_tracking(idx+1, selected_discount_rate, users, emoticons);
        }
        
    }
    
    
    
    
    static void caclulate(int[][] users, int[] selected_discount_rate, int[] emoticons) {
        int cur_membership = 0;
        int cur_price_sum = 0;
        
        for (int[] u : users) {
            int limit_discount = u[0];
            int limit_price = u[1];
            int temp_price_sum = 0;
            
            for (int i = 0; i < m; i++) {
                int cur_discount = selected_discount_rate[i];
                
                // 만약 (내가 허용하는 할인율 > 현재 할인율) -> skip
                if (limit_discount > cur_discount) continue;
                
                // 내 할인율이 더 크면
                int rate = 100 - cur_discount;
                int temp_price = (emoticons[i] * rate) / 100;
                temp_price_sum += temp_price;
            }
            
            // 만약 (임시합 >= limit) -> 멤버쉽 추가
            if (temp_price_sum >= limit_price) {
                cur_membership++;
            }
            // limit 이 더 크면
            else if (temp_price_sum < limit_price) {
                cur_price_sum += temp_price_sum;
            }
        }
        
        // 최종비교
        // 1순위 멤버쉽, 2순위 구매값
        if (max_membership < cur_membership) {
            max_membership = cur_membership;
            max_price_sum = cur_price_sum;
        }
        else if (max_membership == cur_membership) {
            if (max_price_sum < cur_price_sum) {
                max_price_sum = cur_price_sum;
            }
        }
        
    }
    
    
    
}