[프로그래머스/Lv. 2] 이모티콘 할인행사 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
class Solution {
    static int[][] users;
    static int[] emoticons;
    
    static int[] dc, ans;
    static int maxCnt, maxProfit;    // 최대 회원 수, 최대 수익
    
    public int[] solution(int[][] users, int[] emoticons) {
        this.users = users;
        this.emoticons = emoticons;
        
        dc = new int[emoticons.length];    // 이모티콘이 할인되는 퍼센트 저장
        ans = new int[2];
        
        // 이모티콘이 할인되는 분기 모두 탐색 ; 중복 순열 위한 재귀함수
        comb(0);
        
        ans[0] = maxCnt;
        ans[1] = maxProfit;
        
        return ans;
    }
    
    // 이모티콘이 할인되는 모든 분기 탐색 메소드
    private static void comb(int depth) {
        if(depth == dc.length) { // 모든 할인율 적용 시, 할인율 정해진 상태로 회원과 수익 계산
            calculate();
            return;
        }
        
        for(int i = 10 ; i <= 40 ; i += 10) {
           dc[depth] = i;
           comb(depth + 1);
        }
    }
    
    // 회원과 수익 계산 메소드
    private static void calculate() {
        int user = 0;   // 해당 이모티콘 할인율 적용 시 회원 가입 수
        int profit = 0; // 해당 이모티콘 할인율 적용 시 수익
        
        for(int[] u : users) {
            int discount = u[0];
            int price = u[1];
            
            int sum = 0; // 개인이 이모티콘을 구매한 금액의 합
            
            for(int i = 0 ; i < dc.length ; i++) {
                if(dc[i] >= discount) { // 할인 기준이 맞으면 이모티콘 구입
                    sum += (emoticons[i] / 100) * (100 - dc[i]);
                }
            }
            
            if(sum >= price)    user++;         // 가입
            else                profit += sum;  // 수익 올림
        }
        
        // 해당 할인율에 대해 가입한 회원과 수익, 최대값으로 갱신
        if(user > maxCnt) {
            maxCnt = user;
            maxProfit = profit;
            return;
        }
        else if(user == maxCnt) {
            if(maxProfit < profit) {
                maxProfit = profit;
            }
        }
    }
}

✅ 해결 아이디어
✔ 재귀를 이용한 완전탐색
- 시간 복잡도 : 4^7
- 완전탐색 기준 : 이모티콘이 할인되는 경우의 수 (각 이모티콘이 10,20,30,40% 할인되는 분기 탐색)

 

풀이

1) 완전탐색 통해 모든 가능한 할인 조합을 만든다. ⇨ comb 메소드 : 중복순열 위한 재귀함수

2) users 배열과 emoticons 배열을 순회하며 계산 ⇨ calculate 메소드

 

 

---

🔺 다른 풀이들

로직은 비슷한데 List<int[]> 사용하는 코드도 있었다.

(Java) 프로그래머스 - 이모티콘 할인행사

---

💬 느낀 점

으아 완전탐색을 잘하고 싶다!!!

 

뭔가 조합을 만들 생각까지는 했는데,

그 이후에 생각이 멈춰버렸다...

 

그래서 다른 분들 코드 보고 작성했는데 생각하기까지가 어렵지 코드 자체는 그렇게 어려운 편은 아닌 것 같음,,,,

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

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