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

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150368?language=java

프로그래머스

 

풀이 방법

처음으로 할일율을 조절하는 그리디 방법을 생각했으나 할인율이 너무 높아도 안되고 너무 낮아도 안된다고 생각해서 dp 방식을 생각해 봤다. 하지만 dp방식도 이모티콘 개수에 따라, dp 배열이 너무 달려져 완전탐색 방식으로 풀어야겠다고 생각했다.

 

먼저 완전 탐색 방법의 시간 복잡도를 계산해 봤는데 할인이 4가지 경우 밖에 없고 이모티콘도 최대 7개 까지이다. 그러므로  100 * 4 ^ 7이 나와서 시간문제는 통과할 수 있다고 생각했다. 

 

완전 탐색으로 풀이하기 위해 dfs  + 백트레킹 방법을 사용했다. 

dfs(int[][] users, int[] saleRate, int saleRateNum, int[] emoticons) 여기서 saleRate은 미리 만들어 놓은 int[] fixSaleRate = {10, 20, 30, 40}; 배열을 활용해서 인덱스로 할인율을 넘겨주었다. saleRate의 배열은 i번째 이모티콘의 할인율이다. 또 saleRateNum은 지금까지 몇 개까지 할인율을 설정했느냐를 인자로 넘겨주었다.

 

자세한 설명은 코드 주석에 추가했습니다.

import java.util.*;
class Solution {
    int[] fixSaleRate = {10, 20, 30, 40}; // 가능한 할인율을 배열로 저장 
    int n = 0, m = 0, answerNum = 0, answerPrice = 0; // n = user 수, m = 이모티콘 수
    public void cal_buy(int[][] users, int[] saleRate, int[] emoticons) {
        int totalPrice = 0, plusMemberNum = 0; // 이번 할인율에서의 이모티콘 판매 가격과 플러스 가입 증가 수
        for (int i = 0;i < users.length;i++){
            int userPrice = 0; // 현재 유저의 이모티콘 구입 가격 
            for (int j = 0;j < saleRate.length;j++) { // 할인율에 따른 가격 계산 
                if (users[i][0] <= fixSaleRate[saleRate[j]]) {
                    userPrice += (emoticons[j] / 100) * (100 - fixSaleRate[saleRate[j]]);
                }
            }
            if (userPrice >= users[i][1]) { // 일정 가격 넘으면 플러스 멤버 가입
                plusMemberNum += 1;
            }
            else { // 이모티콘 구매
                totalPrice += userPrice;
            }
        }
        if (plusMemberNum > answerNum) {// 플러스 가입이 늘어났다.
            answerNum = plusMemberNum;
            answerPrice = totalPrice;
        }
        else if (plusMemberNum == answerNum){ // 플러스 가입이 같지만 이모티콘 구입 가격이 늘어난 경우
            if (totalPrice > answerPrice)
               answerPrice = totalPrice; 
        }
        return ;
    }
    
    public void dfs(int[][] users, int[] saleRate, int saleRateNum, int[] emoticons) {
        if (saleRateNum == m) { // 할인율을 다 설정함 
            cal_buy(users, saleRate, emoticons); // 전체 가격, 플러스 가입자 수 계산 
        }
        else { // 백트레킹으로 dfs 완전 탐색
            saleRate[saleRateNum] = 0; // 할인율 10%
            dfs(users, saleRate, saleRateNum+1, emoticons);
            saleRate[saleRateNum] = 1; // 할인율 =20%
            dfs(users, saleRate, saleRateNum+1, emoticons);
            saleRate[saleRateNum] = 2; // 할인율 30%
            dfs(users, saleRate, saleRateNum+1, emoticons);
            saleRate[saleRateNum] = 3; // 할인율 40%
            dfs(users, saleRate, saleRateNum+1, emoticons);
        }
    }
    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = new int [2];            
        n = users.length; // 사람 수
        m = emoticons.length; // 이모티콘 수
        int[] saleRate = new int [m];
        for(int i = 0;i < m;i++) {
            saleRate[i] = 0;
        } // 할인율 10%
        dfs(users, saleRate, 1, emoticons);
        saleRate[0] = 1; // 할인율 20%
        dfs(users, saleRate, 1, emoticons);
        saleRate[0] = 2; // 할인율 30%
        dfs(users, saleRate, 1, emoticons);
        saleRate[0] = 3; // 할인율 40%
        dfs(users, saleRate, 1, emoticons);
        answer[0] = answerNum;
        answer[1] = answerPrice;
        return answer;
    }
    
}