[Programmers] 이모티콘 할인행사 JAVA

반응형

728x90

[Programmers] 이모티콘 할인행사 2023 KAKAO BLIND RECRUITMENT - LV2

---

접근

• 완전 탐색 (Brute Force)

---

풀이

카카오 이모티콘 할인행사에서 이모티콘의 할인율이 어떨 때 최고 실적을 낼 수 있는지 구하는 문제이다. 사용자는 각자의 할인율 기준과 비교해 기준에 해당하는 이모티콘은 모두 구입할 때 일정 금액이 넘어가면 이모티콘을 구매하는 대신 이모티콘 플러스를 구독하게 된다. 이모티콘 플러스 구독자 수를 늘리는걸 첫 번째 목표로 잡고 구독을 시킬 수 없다면 판매 수익이 최대인 경우를 구한다. 문제에서 주의할 점은 각 이모티콘은 각각 개별의 할인율을 가지고 있고 할인율은 10, 20, 30, 40으로 4가지만 존재한다. 문제를 제대로 읽지 않아 할인율이 0~100까지에 이모티콘 모두 동일한 할인율을 가진 줄 알고 이진 탐색으로 풀었다가 완전히 코드를 처음부터 새로 짰다.

	int m = emoticons.length; 
        int[] discountRates = {10, 20, 30, 40}; 
        int[] answer = new int[2];

이모티콘의 개수를 따로 변수로 받아뒀고 할인율을 정의한 배열을 선언했다. 배열에 할인율을 넣은 이유는 가능한 모든 조합에서 사용될 할인율을 쉽게 구하기 위해서이다. 그리고 정답으로 출력해야하는 이모티콘 플러스 구독자 수와 수익 금액을 위해 2칸짜리 결과 배열도 만들어 줬다.

	int totalCombinations = (int) Math.pow(4, m);

        for (int i = 0; i < totalCombinations; i++) {
            int[] discounts = new int[m];

            for (int j = 0; j < m; j++) {
                discounts[j] = discountRates[(i / (int) Math.pow(4, j)) % 4];
            }

            evaluateCombination(answer, discounts, users, emoticons);
        }

모든 경우의 수를 구해서 완전 탐색을 진행할 것이기 때문에 할인율의 개수인 4개에 이모티콘 수를 제곱한 만큼 할인율 조합이 생기게 된다. 구해진 경우의 수를 통해 탐색을 진행하는데 각 이모티콘들의 할인율을 저장할 배열을 선언하고 이전에 배열에 넣어뒀던 가능한 할인율을 통해 모든 할인율 조합을 만들게 된다.

discounts[j] = discountRates[(i / (int) Math.pow(4, j)) % 4];

j는 현재 이모티콘의 인덱스로 Math.pow(4, j)는 이모티콘 자릿수를 결정한다. i는 현재 조합된 경우의 수의 인덱스로 i / (int) Math.pow(4, j) i를 특정 자릿수로 나누어 j 번째 자리의 값을 구한다. 그리고 할인율의 개수가 4개이므로 % 4를 해주어 할인율 배열의 인덱스 접근에 맞춰준다. 아마 글을 읽어도 처음 본다면 무슨 소리인지 이해가 가지 않을 것이다.

i= 0, j= 0, percent=10
i= 0, j= 1, percent=10
 ====================== 
i= 1, j= 0, percent=20
i= 1, j= 1, percent=10
 ====================== 
i= 2, j= 0, percent=30
i= 2, j= 1, percent=10
 ====================== 
i= 3, j= 0, percent=40
i= 3, j= 1, percent=10
 ====================== 
i= 4, j= 0, percent=10
i= 4, j= 1, percent=20
 ====================== 
i= 5, j= 0, percent=20
i= 5, j= 1, percent=20

결과를 보면 이해하기 좀 더 쉬울거 같아 인덱스들과 계산된 값을 통해 discountRates 배열에서 가져오는 값을 출력한 일부분이다. 현재 m의 크기는 2로 첫 번째 테스트케이스인 이모티콘의 개수가 2개인 경우 출력문이다. 꼭 이 방법으로 구해야하는 것은 아니기 때문에 이해가 가지 않는다면 대충 이런 식으로 모든 조합의 퍼센트 매칭이 되는구나 정도 이해하고 넘어가면 될 거 같다.

    private static void evaluateCombination(int[] answer, int[] discounts, int[][] users, int[] emoticons) {
        int subscribers = 0;
        int totalRevenue = 0;

        for (int[] user : users) {
            int discountThreshold = user[0];
            int spendingLimit = user[1];
            int spending = 0;

            for (int i = 0; i < emoticons.length; i++) {
                if (discounts[i] >= discountThreshold) {
                    int discountedPrice = emoticons[i] - (emoticons[i] * discounts[i] / 100);
                    spending += discountedPrice;
                }
                
                if(spending >= spendingLimit){
                    subscribers++;
                    break;
                }
            }
            if(spending < spendingLimit)
                totalRevenue += spending; 
        }

현재 할인율 조합을 평가(?) 하는 메서드이다. 그냥 구해진 조합을 통해 계산하는 메서드로 유저들을 순회하며 각 이모티콘의 할인율이 유저의 구매 기준 할인율 보다 높거나 같다면 해당 이모티콘을 할인 된 가격으로 구매하고 총 이모티콘 구매 가격에 더해준다. 만약 현재 구매한 이모티콘 가격이 소비 기준치를 넘어버렸다면 더 이상 순회할 필요가 없으므로 종료해주고 구독자 수를 늘려준다. 소비 기준치 보다 구매가격이 적어 이모티콘 플러스를 구독하지 않았다면 총 수익에 구매가격을 추가해준다.

	//answer[0] = 구독자 수, answer[1] = 총 수익
    if (subscribers > answer[0] || (subscribers == answer[0] && totalRevenue > answer[1])) {
            answer[0] = subscribers; 
            answer[1] = totalRevenue;
        }

현재 할인율 조합으로 구해진 구독자 수가 현재 최대 구독자 수 보다 많거나 구독자 수는 같지만 총 수익이 더 많은 경우 최댓값을 갱신하여 주면 끝이 난다.

---

전체 코드

class Solution {
    public int[] solution(int[][] users, int[] emoticons) {
        int m = emoticons.length; 
        int[] discountRates = {10, 20, 30, 40}; 
        int[] answer = new int[2];

        int totalCombinations = (int) Math.pow(4, m);

        for (int i = 0; i < totalCombinations; i++) {
            int[] discounts = new int[m];

            for (int j = 0; j < m; j++) {
                discounts[j] = discountRates[(i / (int) Math.pow(4, j)) % 4];
            }

            evaluateCombination(answer, discounts, users, emoticons);
        }

        return answer;
    }

    private void evaluateCombination(int[] answer, int[] discounts, int[][] users, int[] emoticons) {
        int subscribers = 0; 
        int totalRevenue = 0; 

        for (int[] user : users) {
            int discountThreshold = user[0]; 
            int spendingLimit = user[1]; 
            int spending = 0; 

            for (int i = 0; i < emoticons.length; i++) {
                if (discounts[i] >= discountThreshold) {
                    int discountedPrice = emoticons[i] - (emoticons[i] * discounts[i] / 100);
                    spending += discountedPrice; 
                }
                
                if(spending >= spendingLimit){
                    subscribers++;
                    break;
                }
            }

            if(spending < spendingLimit)
                totalRevenue += spending; 
        }

        if (subscribers > answer[0] || (subscribers == answer[0] && totalRevenue > answer[1])) {
            answer[0] = subscribers; 
            answer[1] = totalRevenue;
        }
    }
}

---

프로그래머스

이번 문제를 풀며 프로그래머스에서 푼 문제가 400문제가 되었다.