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

[풀이]

문제 조건에서 이모티콘의 최대 개수가 7개밖에 되지 않기 때문에 안심하며 완전탐색을 사용해 풀었다.

각 이모티콘별 할인율을 저장하기 위한 discountRate 변수를 선언했다.

 

setDiscountRate 함수를 통해 각 이모티콘별 할인율을 10프로에서 40프로까지 모든 경우의 수를 돌리도록 지정해줬다.

해당 함수를 통해 각 이모티콘별 할인율을 정해주고 , 모든 이모티콘에 대해 할인율이 정해졌으면 calcPrice 함수를 호출한다.

 

calcPrice 함수에서는 각 사용자마다 이모티콘 총 구매 금액을 계산했다.

각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘들에 할인 가격을 계산하여 price 변수에 더해준다.

모든 이모티콘들에 대해 계산이 끝나면 

각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면 

emoticonPlus(이모티콘 플러스 구매한 사용자 수)에 1을 더해주고 

일정 가격 이상이 되지 않는다면 emoticonPrice에 이모티콘 구매 가격을 더해주었다.

 

1. 이모티콘 플러스 사용자 수 최대

2. 이모티콘 판매액 최대

 

위의 우선순위를 기준으로 이모티콘 플러스 사용자 수와 구매 가격을 계산해주었다.

 

[시간 복잡도]

 

주어진 문제의 조건을 기반으로 시간 복잡도를 계산해보면 

 

1. 완전 탐색

• 각 이모티콘은 4가지 할인율(10%, 20%, 30%, 40%) 중 하나를 선택할 수 있다.
• 이모티콘 개수를 N이라고 하면, 할인율 조합의 경우의 수는 

4^N

 

 

2. calcPrice 함수

 

• 모든 유저에 대해 반복 (users.length = M)
• 각 유저에 대해 이모티콘 개수 만큼 반복 (emoticons.length = N)

따라서 calcPrice의 시간 복잡도는 

 

𝑂(𝑀×𝑁)

 

3. 전체 시간 복잡도

 

𝑂(𝑀×𝑁× 4^N )

 

[코드]

class Solution {
    static final int MAX_EMOTICON = 7;
    static int MAX_USER = 0;
    static int MAX_PRICE = 0;
    static int[] discountRate = new int[MAX_EMOTICON];

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

        setDiscountRate(0,users, emoticons);
        int[] answer = {MAX_USER ,MAX_PRICE};
        return answer;
    }

    public void setDiscountRate(int curIdx, int[][] users, int[] emoticons) {
        if(curIdx == emoticons.length) {
            calcPrice(users,emoticons);
            return;
        }
        for(int i = 10; i<= 40 ; i+=10) {
            discountRate[curIdx] = i;
            setDiscountRate(curIdx+1, users, emoticons);
        }
    }

    public void calcPrice(int[][] users, int[] emoticons) {

        int emoticonPlus=0;
        int emoticonPrice=0;

        for(int[] user : users) {
            // 각 유저의 이모티콘 구매 금액
            int price=0;
            int userDiscountRate = user[0];
            int userPlusPrice = user[1];
            for(int idx=0; idx<emoticons.length; idx++) {
                if(discountRate[idx] >= userDiscountRate) {
                    price += (emoticons[idx]/100) * (100-discountRate[idx]); 
                }
            }
            if(price >= userPlusPrice) {
                emoticonPlus++;
            } else {
                emoticonPrice += price;
            }
        }

        if(emoticonPlus > MAX_USER) {
            MAX_USER = emoticonPlus;
            MAX_PRICE = emoticonPrice;
        } 
        else if ( emoticonPlus == MAX_USER && emoticonPrice >= MAX_PRICE)   MAX_PRICE = emoticonPrice;
    }
}

[문제]

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