이모티콘 할인행사(2023 KAKAO BLIND RECRUITMENT)

문제

코드

import java.util.*;
class Solution {
    static int[] sales;
    static ArrayList<int[]> saleArr=new ArrayList<>();
    static int[] rates={10,20,30,40};
    
    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = {0,0};
        sales=new int[emoticons.length];
        int resultJoin=0;
        int resultMoney=0;     
        makeSales(0,emoticons.length);
        for(int i=0;i<saleArr.size();i++){
            int join=0;
            int money=0;
            for(int j=0;j<users.length;j++){
                int personMoney=0;
                for(int k=0;k<emoticons.length;k++){
                    if(users[j][0]<=saleArr.get(i)[k])
                        personMoney+=emoticons[k]*(100-saleArr.get(i)[k])/100;
                }
                if(personMoney>=users[j][1]) join++;
                else money+=personMoney;
            }
            if(resultJoin<join){
                resultJoin=join;
                resultMoney=money;
            }
            else if(resultJoin==join){
                if(resultMoney<money) resultMoney=money;
            }
        }
        answer[0]=resultJoin;
        answer[1]=resultMoney;
        return answer;
    }
   
    public static void makeSales(int count,int length){
        if(count==length){
            saleArr.add(sales.clone());
            return;
        }
        for(int i=0;i<4;i++){
            sales[count]=rates[i];
            makeSales(count+1,length);
        }
    }
}

풀이

(1) 각 이모티콘의 할인율을 결정할 수 있는 모든 경우의 수를 담는 함수(makeSales())를 실행한다.

• ex) 이모티콘 3개의 할인율이 각각 40%,30%,20% 일때 [40,30,20] 배열을 ArrayList에 저장한다. 이와 같은 방식으로 모든 경우의 수를 saleArr(ArrayList)에 저장한다.

(2) 모든 경우의 수를 담은 saleArr을 순회하면서, 각 할인율 마다 가입자 수와, 판매액을 구해준다.

• 각 할인율마다, 모든 사용자들의 이모티콘 플러스 가입 여부를 판단해야하고, 그러기 위해서 가입자마다 emoticons 배열을 돌면서 이모티콘을 구입하는지 안하는지 판단해야 하기 때문에 총 3중 for문이 만들어진다.

(3) 각 할인율마다 가입자 수와 판매액이 결정되고, resultJoin(결과가 될 가입자 수)와 비교하여 더 많으면, resultJoin을 새로 갱신하여 주고, 같으면 판매액을 비교하여 갱신하여 준다.이 과정을 반복하면 문제를 해결할 수 있다.

결과

나 스스로가 너무 부족하게 느껴졌던 문제이다.
제한사항을 보면, 분명히 이 문제는 brute force로 해결해도 시간초과가 나지 않을 거라는 것을 알고 있었다. 방법을 알고 있으면서도, 도저히 이모티콘 할인율을 결정할 수 있는 모든 경우의 수를 만드는 방법이 떠오르지 않았다. 할인율 총 4개(10%,20%,30%,40%)를 n개의 이모티콘으로 만들수 있는 경우의 수는 4^n개이다. 제한사항에서 이모티콘의 최대 개수는 7개였기 때문에 아무리 많아도 모든 경우의 수는 4^7개이다.
하지만, 그 방법이 떠오르지 않아 다른 사람의 코드를 참고했다.
그 방법이 makeSales()함수이다. 이렇게 간단한 코드인데 왜 그게 생각나지 않았을까.
매번 부족함을 느낀다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges