프로그래머스 - 이모티콘 할인행사

2023 KAKAO BLIND RECUITMENT 이모티콘 할인행사 문제를 풀어보았다.

 

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

프로그래머스

---

문제 설명

 

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

1. 이모티콘 플러스 서비스 가입자를 최대한 늘린다

-> 이모티콘 판매액이 사용자의 기준보다 높으면 이모티콘 플러스 서비스를 가입

-> 이모티콘을 최대한 사게 해서 판매액이 기준보다 높으면 가입을 많이 시킬 것

-> 주어진 사용자의 구매 이모티콘 할인 기준을 충족하는 이모티콘이 많을수록 좋을 것

 

2. 이모티콘 판매액을 최대한 늘리는 것

-> 이모티콘 플러스 서비스에 가입시키지 못한다면 최소 할인율로 구매하도록만 하면 될 것

 

제한 사항

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

이모티콘 할인율 10, 20, 30, 40, 할인율이 들어가는 emoticon의 개수는 7개까지, user는 100명까지

 

따라서 이모티콘 할인율의 경우의 수는 4^7개로 완전탐색을 통해 구현할 수 있을 것 같다.

 

이모티콘 플러스 서비스 가입자 수가 가장많은 경우 가입 수와 이모티콘 구매액을 출력하며,  가입 수가 같을 경우 이모티콘 구매액이 최대인 경우를 구하면 된다. (정렬)

 

---

풀이

import java.util.*;
class Solution {
    class Kakao{
        int total, amount;
        public Kakao(int total, int amount){
            this.total=total; this.amount=amount;
        }
    }
    public static ArrayList<Kakao> answer = new ArrayList<>();
    public static int[] discount = {10, 20, 30, 40};

    public int[] solution(int[][] users, int[] emoticons) {
        int[] dis = new int[emoticons.length];    // 각 인덱스에 이모티콘 할인율이 들어감
        dfs(users, emoticons, dis,0);
        Collections.sort(answer, (a,b) -> a.total == b.total ? b.amount-a.amount : b.total-a.total);
        Kakao k = answer.get(0);
        return new int[]{k.total, k.amount};
    }
    public void dfs(int[][] users, int[] emoticons, int[] dis, int cnt){
        if(cnt == emoticons.length){  // 계산
            int amount = 0;
            int join = 0;
            for(int i=0; i<users.length; i++){
                int sum = 0;
                for(int j=0; j<emoticons.length; j++){
                    if(users[i][0] <= dis[j]) sum += (emoticons[j]/100)*(100-dis[j]); 
                }
                if(sum >= users[i][1]) join +=1;
                else amount += sum;
            }
            answer.add(new Kakao(join, amount));
        }
        else{
            for(int i=0; i<discount.length; i++){
                dis[cnt] = discount[i];
                dfs(users,emoticons,dis,cnt+1);
            }
        }
    }
}

 각 이모티콘에 할인율을 어떻게 반영해줘야할 지 고민이 되었다..

 

따라서 첫 이모티콘부터 dfs를 시작하면서 dis배열에 할인율을 넣어주도록 하였다.

 

        else{
            for(int i=0; i<discount.length; i++){
                dis[cnt] = discount[i];
                dfs(users,emoticons,dis,cnt+1);
            }
        }

dfs를 시작하게되면 dis 배열엔 전부 0이 들어가 있으며 첫 번째 이모티콘부터 10 할인율을 적용하며 첫 번째 if문을 통과할 땐 모든 이모티콘의 할인율이 10일 것이다. 이렇게 되면 맨 마지막 이모티콘부터 10 ~40 할인율 적용, 맨 마지막에서 두 번째가 20일 때 맨 마지막 10~40 적용하는 방식으로 4^7번 작동하게 될 것이다.

이렇게 되면 메모리는 얼마나 잡아먹을까..

제출한 결과

100MB까지 잡아먹기도 한다... 

경우의 수가 많지 않고 모든 경우를 다 따져보려면 어쩔수없는 것인가.. 더 좋은 방법이 없을까 고민이 되었다..

 

시험장에서는 쉽게 못풀었을 것 같다.

정렬 기준에 대한 Comparator, dfs 구현 시 할인율을 어떻게 해야 완전탐색할 수 있을지를 잘 생각해야 했던 문제이다.