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

짱수·2023년 4월 28일

부르트포스

알고리즘 문제풀이

목록 보기

24/26

🔒 문제

문제 링크

🔑 해결 아이디어

우선, 이모티콘의 개수 제한이 최대 7개, 할인 경우의 수는 4가지이므로, 모든 할인 경우의 수를 탐색해도 시간이 넉넉할 것 같았다.
각 할인 경우를 모두 탐색하며 구매자를 갱신했다.

💻 소스코드


import java.lang.*;
import java.util.*;
/*
1. 각 이모티콘의 할인 퍼센테이지를 정한다.
2. 할인 퍼센테이지당의 총 합을 구한다.
3. 해당 퍼센테이지에 대해 구매자를 구한다.
-> 너무 오래 걸릴 것 같긴 한데, 일단 해봐야지 어쩔 수 있나
*/
class Solution {
    User[] user;
    int[] emoticons;
    int maxUser = 0;
    int maxPrice = 0;
    /* user -> 퍼센테이지 별로 리스트를 만든다? 
    40퍼 할인에 대해선 굳이 1~30퍼 유저들을 확인할 필요가 없고, 30퍼 할인에 대해선 1~20퍼 확인할 필요 없다.
    정렬을 하면 될 것 같음
    40퍼 .... 30퍼 ... 20퍼 ... 10퍼 ... 하면 딱 끊을 수 있고 좋겠네*/
    
    /* emoticons -> 할인 퍼센테이지 별 총 합만 계속 갱신해도 좋을 것 같음*/
    public int[] solution(int[][] users, int[] emoticons) {
        //4:45 ~ 5:10 (휴식) / 10:00 ~ 11:35 (85점) / ~11:40 (해결)
        int[] answer = new int[2];
        //부르트포스 비슷한 알고리즘을 사용할 것 같음
        //BFS??? -> 이건듯, 모든 할인 경우 다 체크해야함
        //dp??
        int[] discount = new int[4];
        user = new User[users.length];
        this.emoticons = emoticons;
        for(int i = 0; i<users.length; i++){
            user[i] = new User(users[i][0], users[i][1]);
        }        
        Arrays.sort(user);
        
        calc(discount, 0);
        /*for(int i = 0; i<user.length; i++)
            System.out.println(user[i]);*/
        answer[0] = this.maxUser;
        answer[1] = this.maxPrice;
        return answer;
    }
    
    //discountList == 40퍼, 30퍼, 20퍼, 10퍼
    public void calc(int[] discountList, int idx){
        
        int price = emoticons[idx];
        
        for(int i = 0; i<4; i++){
            discountList[i] += price;
            nextStep(discountList, idx);
            discountList[i] -= price;
        }
    }
    
    private void nextStep(int[] discountList, int idx){
        if(idx == emoticons.length-1){
            /*
            for(int i = 0; i<4; i++){
                System.out.print(discountList[i] + " ");
            }
            System.out.print(" : ");
            */
            getUser(discountList);
        }
        else {
            calc(discountList, idx+1);
        }
    }
    //7000 -> 40% 1600*60 = 
    
    //discount == 몇퍼센트 할인은 총 얼마입니다.
    private void getUser(int[] discountList){
        int maxUser = 0;
        int maxPrice = 0;
        int[] totalDiscount = discountList.clone();
        totalDiscount[0] *= 6;        
        totalDiscount[1] *= 7;
        totalDiscount[2] *= 8;
        totalDiscount[3] *= 9;
        for(int i = 0; i<4; i++)
            totalDiscount[i] /= 10;
        
        for(int i = 1; i<=3; i++)
            totalDiscount[i] += totalDiscount[i-1];
        
        for(int i = 0; i<user.length; i++){
            int idx;
            switch(user[i].buyHuddle){
                case 40:
                    idx = 0;
                    break;
                case 30:
                    idx = 1;
                    break;
                case 20:
                    idx = 2;
                    break;
                case 10:
                    idx = 3;
                    break;
                default:
                    continue; 
            }
            if(user[i].emoticonPlusHuddle <= totalDiscount[idx])
                maxUser++;
            else
                maxPrice += totalDiscount[idx];
            
        }
        
        if(maxUser > this.maxUser){
            this.maxUser = maxUser;
            this.maxPrice = maxPrice;
            
        }
        else if(maxUser == this.maxUser && maxPrice >this.maxPrice)
            this.maxPrice = maxPrice;
    }
    
}
class User implements Comparable<User>{
    int buyHuddle;
    int emoticonPlusHuddle;
    
    public User(int buyHuddle, int emoticonPlusHuddle){
        this.emoticonPlusHuddle = emoticonPlusHuddle;
       if(buyHuddle > 30)
            this.buyHuddle = 40;
        else if(buyHuddle > 20)
            this.buyHuddle = 30;
        else if(buyHuddle > 10)
            this.buyHuddle = 20;
        else
            this.buyHuddle = 10;
    }
    
    public int compareTo(User u2){
        if(this.buyHuddle == u2.buyHuddle){
            return this.emoticonPlusHuddle - u2.emoticonPlusHuddle;
        }
        return this.buyHuddle - u2.buyHuddle;
    }
    
    public String toString(){
        return this.buyHuddle + " " + this.emoticonPlusHuddle;
    }
    
    
}
/*
    만약 모두 10%인데 산 사람이 있으면 조금 올렸을 때 확인할 필요가 없다?
    4900
    2800
    ----
    7700 -> 770 * 6 = 4620
    
    1600 * 0.8 --> 1280
*/