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

🔒 문제

문제 링크

🔑 해결 아이디어

우선, 이모티콘의 개수 제한이 최대 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
*/

⭐️ 참고

할인 가격을 계산하는 코드가 수정되었다.

• 수정 전 :
  totalDiscount[0] *= 0.6; ...
• 수정 후 :
  totalDiscount[0] *= 6;
totalDiscount[0] /= 10;

수정 이전의 85점 결과가 수정 이후 100점으로 바뀌었다.
아마, 수정 이전의 코드는 계산 결과가 정수와 실수 사이의 계산이므로 부동소수점에 의한 오차가 생기는 반면, 수정 이후의 코드는 정수 사이의 계산으로 결과값이 항상 정수이기 때문인 것 같다.

앞으로도 정수와 실수 사이의 계산에 있어서는 오차를 예방하기 위해 항상 정수 값으로 계산을 해 주자.