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

링크

 

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

프로그래머스

 

설명

문제의 제한 사항을 먼저 읽어봅니다.

할인이 가능한 경우의 수는 4개(10%, 20%, 30%, 40%) 이모티콘의 최대 수도 7개입니다.

이 경우 할인으로 나올 수 있는 이모티콘의 경우의 수는 4^7 = 16384 로 경우의 수가 굉장히 적습니다.

여기에 유저마다 비교한다고 해도 user는 100명까지가 최대로 해당 경우의 수도 매우 적습니다.

 

따라서 그리디 or 완전탐색으로 풀 수 있다고 판단하였습니다.

 

문제에서 플러스 이모티콘 구매 숫자가 높은 것이 1순위, 이모티콘 판매 비용이 높은 것이 2순위이기 때문에

정렬 순서를 플러스 이모티콘 구매 숫자 -> 이모티콘 판매 비용로 정합니다.

 

위에 정의한 조건에 따라 구현하면 완료가 됩니다. 

 

1. 각 유저의 구매 조건을 저장합니다. (BuyDecision)
2. 이모티콘 할인율에 따른 모든 경우의 수를 재귀를 통해 구합니다. 
3. 각 할인율을 유저마다 가격의 합을 구한 후 이모티콘을 구매할 지, 아니면 이모티콘 플러스를 구매할 지 결정합니다.
4. 위에서 정의한 정렬 순서에 따라 가장 높은 순서의 값을 결정합니다.
(필자는 결과값이 1개만 필요하여 조건문으로 풀었습니다.)

 

 

풀이

import java.util.*;

class Solution {
    int[] casePercent = new int[]{10, 20, 30, 40};
    List<BuyDecision> userBuyDecisions = new ArrayList<>();
    int maxPlusEmoticonCount = 0;
    int maxEmoticonSellPrice = 0;
    
    public int[] solution(int[][] users, int[] emoticons) {
        // 할인 경우의 수 4^7 = 16384개밖에 안됨
        // 그리디 예상
        
        
        // 목적
        // 1. 사용자 수
        // 2. 판매액 최대
        
        for (int i=0; i<users.length; i++) {
            int[] user = users[i];
            int discountPercent = user[0];
            int plusEmoticonDecisionAmount = user[1];
            userBuyDecisions.add(new BuyDecision(discountPercent, plusEmoticonDecisionAmount));
        }
        
        int[] current = new int[emoticons.length];
        // 모든 경우의 수에 대해 한번씩 훑기
        getCombinations(0, current, emoticons);
        
        
        return new int[]{maxPlusEmoticonCount, maxEmoticonSellPrice};
    }
    
    public void getCombinations(int index, int[] current, int[] emoticons) {
        if(index == current.length) {
            int[] discountedPrices = new int[emoticons.length];
            for (int i=0; i<emoticons.length; i++) {
                int emoticonPrice = emoticons[i];
                int discountPercent = current[i];
                int discountedPrice = emoticonPrice * (100 - discountPercent) / 100;
                discountedPrices[i] = discountedPrice;
            }
            // user와 함꼐 가격 계산
            int plusBuyCount = 0;
            int totalEmoticonSellPrice = 0;
            for (BuyDecision buyDecision: userBuyDecisions) {
                int emoticonSellPrice = 0;
                for (int i=0; i<discountedPrices.length; i++) {
                    int emoticonPrice = emoticons[i];
                    int discountPercent = current[i];
                    int discountedPrice = discountedPrices[i];
                    // 구매 결정
                    if (discountPercent >= buyDecision.getDiscountPercent()) {
                        // 할인율이 높으니까 산다.
                        emoticonSellPrice += discountedPrice;
                    }
                }
                // 이모티콘 플러스 살 가격이면 산다.
                if (emoticonSellPrice >= buyDecision.getPlusEmoticonDecisionAmount()) {
                    plusBuyCount++;
                } else {
                    // 안사고 따로 판매한다.
                    totalEmoticonSellPrice += emoticonSellPrice;
                }
            }
            
            if (plusBuyCount > maxPlusEmoticonCount) {
                maxPlusEmoticonCount = plusBuyCount;
                maxEmoticonSellPrice = totalEmoticonSellPrice;
            } else if (plusBuyCount == maxPlusEmoticonCount) {
                maxEmoticonSellPrice = Math.max(maxEmoticonSellPrice, totalEmoticonSellPrice);
            }
            
            return;
        }
        
        for(int value: casePercent) {
            current[index] = value;
            getCombinations(index+1, current, emoticons);
        }
    }
}

class BuyDecision {
    int discountPercent;
    int plusEmoticonDecisionAmount;
    
    public BuyDecision(int dp, int peda) {
        this.discountPercent = dp;
        this.plusEmoticonDecisionAmount = peda;
    }
    
    public int getDiscountPercent() {
        return discountPercent;
    }
    
    public int getPlusEmoticonDecisionAmount() {
        return plusEmoticonDecisionAmount;
    }
}