[프로그래머스 lv.2 - 150368] 이모티콘 할인행사 // Java 재귀, DFS

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

프로그래머스

 

이모티콘의 최대 개수가 7개, 할인율의 종류가 4개이므로 최대 4^7 경우의 수를 탐색해야했다.

재귀를 써본적이 없어서 7중 for문을 써서 풀려고 했다 😅 하지만 이모티콘의 개수에 따라 for문을 다르게 중첩해야 하기에 그렇게 풀기는 어려웠다.

 

재귀를 써서 DFS로 풀기로 하고 함수를 작성했다.

<로직>

할인율의 조합을 담는 rates 배열을 가지고 재귀호출을 하면서, rates 배열의 모든 경우의 수를 탐색.

재귀함수가 처음 호출될 때는 rates배열이 다 0으로 초기화되어있다. 호출 될 때마다, 현재 index에 할인율을 지정된 할인율을 담음. 지정된 할인율은 재귀호출의 파라미터로 넘어오는데, 0~3의 인덱스로 각 RATES[idx]로 표현된다.

할인율을 담았으면 현재 길이를 확인한다. cur + 1 == emoticons.length  이면 재귀를 종료하고 문제에서 요구한 계산 실행.

아직 length가 부족하면 다음 할인율을 담아야하니 재귀호출을 한다. 이 때, 현재 rates의 배열에서 파생되는 모든 경우의 수(다음거 10, 20, 30, 40)를 탐색해야하므로 모든 경우의 수에 대해 재귀호출을 한다. 하나의 재귀 프로세스는 rates가 꽉차서 계산이 실행될때만 종료되기 때문에, 메모리걱정은 안해도 된다.\

문제에서 요구하는 계산 = 그냥 할인율,이모티콘 곱해서 가격구하고 몇명이 사는지, 그리고 최대인원이 살 때 매출 얼마인지. ==> MAXREG 변수가 최대로 갱신될 때 MAXREV 갱신. MAXREG가 동률일 때 MAXREV 비교

 

<구현>

 

 

DFS를 처음 짜봤는데, search함수 내에서 calculate라는 함수를 미리 넣어놓고, 나중에 짰다. 이렇게 하니까 search함수의 재귀 종료 시점에서 어떤 계산이 일어나야하는지, 그 때 필요한 파라미터는 뭐가있는지, 어떤 반환값을 가져야하는지를 미리 생각해볼 수 있어서 좋은 것 같다.

 

import java.util.*;
class Solution {
    public static int MAXREG = 0;
    public static int MAXREV = 0;
    public static int[] RATES = {10, 20, 30, 40};
    
    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = new int[2];
        int[] rates = new int[emoticons.length];
        for(int i = 0; i< RATES.length; i++){
            search(users, emoticons, rates, 0, i);
        }
        
        answer[0] = MAXREG;
        answer[1] = MAXREV;
        return answer;
    }
    
    public static void search(int[][] users, int[] prices, int[] rates, int cur, int idx){
        rates[cur] = RATES[idx];
        if (cur + 1 == rates.length){
            int[] infos = calculate(users, prices, rates);
            if (infos[0] > MAXREG){
                MAXREG = infos[0];
                MAXREV = infos[1];
            }
            else if (infos[0] == MAXREG){
                MAXREV = Math.max(MAXREV, infos[1]);
            }
        }
        else{
            for(int i = 0; i<RATES.length; i++){
                search(users, prices, rates, cur + 1, i);
            }
        }
    }
    
    public static int[] calculate(int[][] users, int[] prices, int[] rates){
        int[] ans = {0,0};
        
        for (int[] user:users){
            int buyrate = user[0];
            int buylimit = user[1];
            int pricesum = 0;
            for(int i = 0; i<prices.length; i++){
                if(rates[i] >= buyrate){
                    pricesum += (100 - rates[i]) * prices[i] / 100;
                }
            }
            if (pricesum >= buylimit){
                ans[0] += 1;
                pricesum = 0;
            }
            else{
                ans[1] += pricesum;
            }
        }
        return ans;
        
    }
}