[프로그래머스] 이모티콘 할인행사 / 자바(Java)

문제

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

프로그래머스

 

---

해설

문제를 읽다보면 확실히 해야하는 부분이 있습니다.

 

1. 이모티콘 플러스의 구매 여부는 각 사용자의 예산 한도를 넘기는 경우이다 -> 사용자를 기준으로 최종 구매 연산을 하며 모든 사용자는 각 이모티콘별로 동일한 할인율을 가져야 한다. -> 할인율들이 정해진 후 최종 구매연산이 가능하다.

2. 할인율은 10, 20, 30, 40% 로 이루어진다 -> 각 이모티콘별로 4가지의 가능성이 있다.

3. 사용자의 길이는 100이하이며 이모티콘의 길이는 최대 7개이다 -> 입력값이 작다.

 

즉 3번의 이유로 완전탐색을 고려해 보게 되며, 1번에의해 탐색 중간의 가지치기는 불가능함을 알수 있다.

모든 가능성을 보기위해 조합을 사용해 이모티콘들의 할인율들의 조합이 되는 모든 가능성을 구하고 이에 맞추어 사용자기준 최종 구매연산을 통해 원하는 답의 조건을 구하면 해결이 가능하다.

 

주의점

• users와 emoticons의 길이는 비교적 짧다
• 목표 조건은 가능한 많은 플러스 가입자를 늘리며 가입자가 같은 경우 매출액이 높도록 한다.

---

코드

class Solution {
    
    int emoServ = 0;
    int earn = 0;
    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = new int[2];
        // 각 이모티콘의 할인율이 담길 배열
        int[] arr =new int[emoticons.length];
        
        comb(arr,0,users,emoticons);
        
        answer[0]=emoServ;
        answer[1]=earn;
        
        return answer;
    }
    //조합을 통해 이모티콘들이 가지는 할인율의 모든 가능성을 구한다.
    public void comb(int[] arr,int index,int[][] users,int[] emoticons){
        
        if(index==arr.length){
            cal(arr,users,emoticons);
            return;
        }
        
        for(int i=10;i<=40;i+=10){
            arr[index]=i;
            comb(arr,index+1,users,emoticons);
        }
        
    }
    // 정해진 할인율을 각 사용자 별로 서비스 가입 수 및 매출액을 구한다.
    public void cal(int[] arr,int[][] users,int[] emoticons){
        
        int curCount=0;
        int curEarn=0;
        
        for(int[] user:users){
            int discount= user[0];
            int price =user[1];
            int sum=0;
            
            for(int i=0;i<arr.length;i++){
                if(arr[i]>=discount) sum+=(emoticons[i]/100)*(100-arr[i]);
            }
            
            if(sum>=price) curCount++;
            else curEarn+=sum;
  
        }
        
        
        if(curCount>emoServ){
            emoServ=curCount;
            earn=curEarn;
            return;
        }    
        else if(curCount==emoServ && earn<curEarn){
                earn=curEarn;
        }
    }
}