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

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/150368

프로그래머스

문제 요약 :

1. 이모티콘 플러스 판매량을 최대로 하는 각 이모티콘의 할인률 구하기
2. 같은 이모티콘 플러스 판매량에 대해 최대 이익을 가지는 각 이모티콘의 할인률 구하기

문제 풀이 시간 : 1시간

문제 성공 여부 : 성공

 

접근 방법 :

1. 할인률은 10, 20, 30, 40 네 가지 경우밖에 없음
2. 사용자는 최대 100명
3. 이모티콘은 최대 7개
4. 4^7 = 2^14 = 16000 정도이므로 모든 사용자를 탐색해도 1,600,000 가지
5. 따라서 모든 이모티콘 각각에 할인률을 순열로 돌려 완전탐색

 

핵심 로직

   static void dfs(int s){
        if(s==hal.length || hal[s]>40) return; // hal : 할인율
        sol(); // 모든 유저에 대한 이모티콘 구입 계산
        
        hal[s]+=10;
        dfs(s);
        hal[s]-=10;
        dfs(s+1);
    }

 

모든 이모티콘에 각각의 할인률을 넣는 dfs 함수이다.

모든 이모티콘에 할인률을 설정하면 sol() 함수를 호출해 모든 유저에 대해 이모티콘 구입을 계산한다.

 

핵심로직2

    static void sol(){
        int cnt = 0, toal_buy = 0;
        
        for(int i = 0; i<u.length; i++){
            int buy = 0;
            
            for(int j = 0; j<hal.length; j++)
                if(u[i][0] <= hal[j]) 
                    buy += emo[j] - (emo[j] * hal[j] / 100);
            
            if(buy>=u[i][1]) cnt++;
            else toal_buy += buy;
        }
        
        
        if(a < cnt) { a = cnt; b = toal_buy; }
        else if(a==cnt && b<toal_buy) b = toal_buy;
    }

 

sol() 함수에서는 dfs에서 정해진 각각의 이모티콘 할인률에 대해 모든 유저들의 니즈에 맞게 계산을 수행한다.

 

만약 고객의 최소 할인률을 충족하는 상품이면 total_buy에 할인된 가격을 추가하고 최대 구매 가능 수치를 넘기면 cnt를 올려준다

 

이후 cnt를 전역변수 a와 비교하여 더 높을 경우 최신화를 해주는 과정을 반복한다.

 

 

성공 코드 :

import java.util.*;
class Solution {
    static int[][] u; // 유저배열
    static int[] emo,hal; // emo: 이모티콘, hal: 할인율
    static int a, b; // a: 가입 수, b: 매출액
    
    static void sol(){
        int cnt = 0, toal_buy = 0;
        
        for(int i = 0; i<u.length; i++){ // 모든 유저에 대해 지출액 계산
            int buy = 0;
            
            for(int j = 0; j<hal.length; j++)
                if(u[i][0] <= hal[j]) 
                    buy += emo[j] - (emo[j] * hal[j] / 100);
            
            if(buy>=u[i][1]) cnt++;
            else toal_buy += buy;
        }
        
        
        if(a < cnt) { a = cnt; b = toal_buy; }
        else if(a==cnt && b<toal_buy) b = toal_buy;
    }
    
    static void dfs(int s){
        if(s==hal.length || hal[s]>40) return;
        sol();
        
        hal[s]+=10;
        dfs(s);
        hal[s]-=10;
        dfs(s+1);
    }
    
    public int[] solution(int[][] users, int[] emoticons) {
        u = users;
        emo = emoticons;
        hal = new int[emoticons.length];
        Arrays.fill(hal,10);
        
        dfs(0);
        
        return new int[]{a,b};
    }
}