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

문제 링크

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

프로그래머스

💡 풀이

우선, 문제의 조건을 확인해보면 이모티콘의 할인율은 10, 20, 30, 40(%)로 고정되어 있고, 입력으로 들어오는 이모티콘 종류의 개수도 최대 7개 입니다. 따라서, 재귀를 이용한 완전 탐색으로 구현했습니다. 

 

재귀 함수는 이모티콘을 기준으로 진행됩니다. 재귀 함수의 파라미터에 index를 전달해 이모티콘 배열에 순차적으로 접근하도록 했습니다.

Recursive Case

재귀 함수 안에서 정해진 할인율 4가지(10, 20, 30, 40)에 대해 모두 탐색을 시도합니다.

...
for(int i = 0; i < 4; i++) {
    int rate = discountRate[i];
    int discountPrice = emoticons[index] * (100 - rate)/100;

    emoList.add(new Emoticon(rate, discountPrice));
    recurEmoticons(users, emoticons, index + 1);
    emoList.remove(emoList.size() - 1);
}
...

여기서 emoList는 Emoticon 객체의 배열입니다. Emoticon 클래스는 아래와 같이 구성되어 있습니다. 

static class Emoticon {
    int rate;
    int price;

    Emoticon(int rate, int price) {
        this.rate = rate;
        this.price = price;
    }
}

rate는 해당하는 이모티콘의 할인율, price는 할인율을 적용한 이모티콘의 가격을 의미합니다. 

 

다시, 위의 반복문으로 돌아가보면, 탐색하고자하는 할인율과 이를 적용시킨 이모티콘의 가격으로 새로운 Emoticon 객체를 만들고 리스트에 넣고 index를 1 증가시켜 재귀를 진행합니다. 

 

Base Case

재귀 함수가 종료되는 Base Case의 조건은 파라미터로 넘겨진 index가 이모티콘 배열의 길이와 같을 경우입니다. 이때, 할인을 적용한 모든 이모티콘이 emoList에 담겨있을 것이고 이를 users 배열과 비교하며 이모티콘 플러스 서비스 가입자와 이모티콘 판매액을 계산합니다. 

 

우선, Base Case입니다. 

...
// Base Case
if(index == emoticons.length) {
    int[] result = proceedUser(users);
    if(answer[0] < result[0]) {
        answer = result.clone();
    } 
    if(answer[0] == result[0] && answer[1] < result[1]) {
        answer = result.clone();
    }
    return;
}
...

proceedUser() 메서드의 결과로 나온 [이모티콘 플러스 서비스 가입자, 이모티콘 판매액] 배열을 기존과 비교합니다. 문제에서 이모티콘 플러스 서비스 가입자가 많은 것을 우선시 했기 때문에 먼저 조건을 확인합니다. 

 

각 사용자에 대해 계산하는 proceedUser 메서드는 아래와 같습니다. 

static int[] proceedUser(int[][] users) {
    int plusMember = 0;
    int totalPrice = 0;

    for(int i = 0; i < users.length; i++) {
        int userWishRate = users[i][0];
        int userMaxPrice = users[i][1];

        int userPurchasePrice = 0;
        for(Emoticon emo : emoList) {
            if(userWishRate <= emo.rate) {
                userPurchasePrice += emo.price;
            }
        }

        // 사용자의 허용 가격 이상의 돈을 구매에 사용한 경우
        if(userPurchasePrice >= userMaxPrice) {
            plusMember++; // 임티플 가입
        }
        else {
            totalPrice += userPurchasePrice; // 아닐 경우, 이모티콘 구매
        }
    }

    return new int[]{plusMember, totalPrice};
}

emoList를 돌며, 사용자가 원하는 할인율 이상으로 할인할 경우 구매를 시도하고 모든 이모티콘에 대해 구매가 완료되면, 사용자의 가격 기준과 비교해 이모티콘 플러스 가입 여부를 결정합니다. 이 결과를 위의 Base Case에서 사용합니다. 

 

전체 코드 

전체적인 코드는 다음과 같습니다. 

import java.util.*;

class Solution {
    static int[] discountRate = {10, 20, 30, 40};
    static int[] answer = new int[2];
    static List<Emoticon> emoList = new ArrayList<>();
    
    public int[] solution(int[][] users, int[] emoticons) {
        recurEmoticons(users, emoticons, 0);
        return answer;
    }
    
    static void recurEmoticons(int[][] users, int[] emoticons, int index) {
        // Base Case
        if(index == emoticons.length) {
            int[] result = proceedUser(users);
            if(answer[0] < result[0]) {
                answer = result.clone();
            } 
            if(answer[0] == result[0] && answer[1] < result[1]) {
                answer = result.clone();
            }
            return;
        }
        
        for(int i = 0; i < 4; i++) {
            int rate = discountRate[i];
            int discountPrice = emoticons[index] * (100 - rate)/100;
            
            emoList.add(new Emoticon(rate, discountPrice));
            recurEmoticons(users, emoticons, index + 1);
            emoList.remove(emoList.size() - 1);
        }
    }
    
    static int[] proceedUser(int[][] users) {
        int plusMember = 0;
        int totalPrice = 0;
        
        for(int i = 0; i < users.length; i++) {
            int userWishRate = users[i][0];
            int userMaxPrice = users[i][1];
            
            int userPurchasePrice = 0;
            for(Emoticon emo : emoList) {
                if(userWishRate <= emo.rate) {
                    userPurchasePrice += emo.price;
                }
            }
            
            // 사용자의 허용 가격 이상의 돈을 구매에 사용한 경우
            if(userPurchasePrice >= userMaxPrice) {
                plusMember++; // 임티플 가입
            }
            else {
                totalPrice += userPurchasePrice; // 아닐 경우, 이모티콘 구매
            }
        }
        
        return new int[]{plusMember, totalPrice};
    }
    
    static class Emoticon {
        int rate;
        int price;
        
        Emoticon(int rate, int price) {
            this.rate = rate;
            this.price = price;
        }
    }
}