프로그래머스 코딩테스트 문제 - [Lv.2] 이모티콘 할인행사 (Java)

📌 문제

문제 출처 - 링크

문제 설명

알고리즘 분류

• 구현
• 완전 탐색 (브루트포스)
• DFS (재귀)

📋 문제 요약 설명

• 이모티콘마다 할인율은 다를 수 있으며 할인율은 10%, 20%, 30%, 40% 중 하나로 설정된다.
• 사용자는 이코티콘을 구매할 때 정해진 할인율 이상이 되어야지 구매한다. 그리고 할인율 이상인 이모티콘은 모두 구매한다.
• 이모티콘 구매 비용의 합이 일정 금액 이상이 되면 이모티콘 구매를 모두 취소하고, 이모티콘 플러스를 가입한다.
• 이모티콘 플러스 가입자를 최대한 늘리면서 이모티콘 판매액도 가장 많을 때 값을 반환하라

💡 알고리즘 설계 / 접근 방법

• 이모티콘의 할인율을 조합해야 하는데 이모티콘 플러스 서비스에 가장 많이 가입하도록 하기 위해서는 모든 조건을 찾아보는 수밖에 없을 것 같아서 완전 탐색을 생각하게 되었다.
• 완전 탐색을 하려면 모든 조합을 만들어야 하므로 재귀로 구현해야겠다 생각했고, DFS의 재귀 방식을 선택하게 되었다.

1. 재귀 함수를 사용하기 위해서 메소드를 만든다.
2. 이모티콘마다 10%, 20%, 30%, 40% 중 할인율을 할당하고, 모두 할인율이 정해지면 해당 조합이 최적의 조합인지 확인한다.
   • 이모티콘의 할인률을 할당한 다음 재귀 함수를 호출해서 모든 조합을 만들도록 한다.
   • 조합은 [10, 10, 10, 10] → [10, 10, 10, 20] → [10, 10, 10, 30] … 순서로 만들어진다.
3. 최적의 조합인지 확인하기 위한 메소드를 만든다.
4. 사용자마다 이모티콘 구매 비용을 계산하고, 이모티콘 플러스 가입 여부도 확인한다.
5. 해당 조합의 총 이모티콘 플러스 가입자 수와 이모티콘 구매 비용으로 이전의 기록과 비교한다.

➕ 보완하기 / 성능 비교

• 작성한 코드 형태가 백트래킹 패턴과 동일하긴 하나 가지치기 없이 전 조합을 평가하기 때문에 백트래킹이라고 보긴 어렵다. 하지만 백트래킹으로도 구현할 수 있는 문제이다.

✅ 풀이

시간 복잡도 → O($4^m \cdot (u \cdot m)$)

1. 할인 조합 생성 부분 (setRateRecur) : O($4^m$)
2. 조합 평가 부분 (findComb) : O(u⋅m)
   • 사용자 수: u
   • 이모티콘 수: m

class Solution {
    static int EMOTICON_PLUS; // 총 이모티콘 플러스 서비스 가입자수
    static int TOTAL_SALES; // 총 이모티콘 구매 비용
    static final int[] SALE_RATE = {10, 20, 30, 40}; // 이모티콘 할인율
    
    public int[] solution(int[][] users, int[] emoticons) {
        EMOTICON_PLUS = 0; // 매 테스트 케이스 호출마다 초기화
        TOTAL_SALES = 0;
        
        setRateRecur(users, emoticons, 0, new int[emoticons.length]);
        return new int[] {EMOTICON_PLUS, TOTAL_SALES};
    }
    
    // 재귀 기반 DFS 방식으로 완전 탐색을 수행해 이모티콘 할인율 조합 생성
    private void setRateRecur(int[][] users, int[] emoticons, int index, int[] rates) {
        // index: 몇 번째 이모티콘에 접근했는지, rates: saleRate 중 이모티콘에 적용할 할인율 담는 배열
        
        // 제일 마지막 이모티콘까지 재귀 호출되었다면, 최적의 할인율 조합인지 확인
        if (index == emoticons.length) {
            findComb(users, emoticons, rates);
            return;
        }
        
        for (int rate : SALE_RATE) {
            rates[index] = rate;
            // 다음 이모티콘의 할인율을 정하러 재귀함수 사용
            setRateRecur(users, emoticons, index + 1, rates);
        }
    }
    
    // 최적의 이모티콘 할인율 조합인지 확인
    private void findComb(int[][] users, int[] emoticons, int[] rates) {
        int emoticonPlus = 0; // 현재 할인율 조합의 이모티콘 플러스 가입자수
        int totalSales = 0; // 현재 할인율 조합의 이모티콘 구매 비용
        
        for (int[] user : users) {
            int purchase = 0; // 이모티콘 구매 비용
            int rate = user[0]; // 해당 할인율 이상이어야 사용자가 이모티콘을 구매함
            int maxPurchase = user[1]; // 사용자가 지불 가능한 최대 이모티콘 구매 비용
            
            for (int i = 0; i < rates.length; i++) {
                // 이모티콘 할인율이 더 크다면 이모티콘을 구매함
                if (rate <= rates[i]) {
                    purchase += (emoticons[i] * (100 - rates[i]) / 100);
                }
            }
            
            // 최대 이모티콘 구매 비용 이상이 되면 이모티콘 플러스 가입 
            if (maxPurchase <= purchase) emoticonPlus++;
            // 아니면 이모티콘 구매 비용 업데이트
            else totalSales += purchase;
        }
        
        // 현재 할인율 조합의 이모티콘 플러스 가입자수가 많다면 총 결과 업데이트
        if (EMOTICON_PLUS < emoticonPlus) {
            EMOTICON_PLUS = emoticonPlus;
            TOTAL_SALES = totalSales;
        }
        // 이모티콘 플러스 가입자수가 같으면 더 큰 이모티콘 구매 비용으로 업데이트
        else if (EMOTICON_PLUS == emoticonPlus) {
            TOTAL_SALES = Math.max(totalSales, TOTAL_SALES);
        }
    }
}