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

🧩 문제 정보

• 문제: https://school.programmers.co.kr/learn/courses/30/lessons/150368
• 난이도: LV 2
• 유형: 완전탐색, 백트랙킹

NewCodes의 풀이

• 스스로 풀었는가: O
• 다시 풀어볼 문제인가: O
• 풀이 시간: 60분
• 제출 횟수: 1회
• 선택 언어: Java
• 풀이 환경: 프로그래머스 내 IDE

---

📝 풀이 정보

요구 사항 정리

1. 최적해 우선순위: 가입자 수, 총판매액
2. 사용자 n명, 이모티콘 m개
3. 할인율: 10, 20, 30, 40 중 하나
4. 구매 조건: 할인율 이상이어야 구매, 특정 금액 이상이면 플러스 가입
5. 정답: 최적의 상황일 때 가입자 + 판매액 리턴

 

 

리팩토링한 코드 (정돈된 풀이)

import java.util.*;

class Solution {
    private int[][] users;
    private int[] emoticons;
    private int[] sale = {10, 20, 30, 40};
    private int[] answer = new int[2];
    
    public int[] solution(int[][] users, int[] emoticons) {
        this.users = users;
        this.emoticons = emoticons;
        int[] rates = new int[emoticons.length];
        
        back(rates, 0);
        
        return answer;
    }
    
    private void back(int[] rates, int depth) {
        if (depth == rates.length) {
            checkOptimalAnswer(rates);
            
            return;
        }
        
        for (int i = 0; i < sale.length; i++) {
            rates[depth] = sale[i];
            back(rates, depth + 1);
        }
    }
    
    private void checkOptimalAnswer(int[] rates) {
        int[] result = new int[2];
        
        for (int i = 0; i < users.length; i++) {
            int totalPurchase = 0;
            
            for (int j = 0; j < emoticons.length; j++) {
                if (users[i][0] <= rates[j]) {
                    totalPurchase += emoticons[j] * (100 - rates[j]) / 100;
                }
            }
            
            if (totalPurchase >= users[i][1]) { // 이모티콘 플러스 구입
                result[0]++;
            } else {
                result[1] += totalPurchase;
            }
        }
        
        if (result[0] > answer[0]) {
            answer[0] = result[0];
            answer[1] = result[1];
        }
        
        if (result[0] == answer[0] && result[1] > answer[1]) {
            answer[0] = result[0];
            answer[1] = result[1];
        }
    }
}

 

풀이 의도 설명

 : 해당 풀이에서 포인트는 백트랙킹입니다. 백트랙킹을 통해 각각의 이모티콘의 할인율을 완전탐색하고 있습니다. 문제에서 주어진 두 번째 테스트케이스를 통해 어떤 식으로 완전탐색되는지 아래에 표현했습니다.

 

10, 10, 10, 10

10, 10, 10, 20

10, 10, 10, 30

10, 10, 10, 40

10, 10, 20, 10

10, 10, 20, 20

10, 10, 20, 30

10, 10, 20, 40

...(생략)

 

depth는 현재 어떤 이모티콘에 접근해있는지 알려주는 index 역할을 합니다. 제일 마지막 이모티콘까지 재귀 호출되었다면, checkOptimalAnswer()를 통해 최적의 해인지 체크합니다. 

 

해당 풀이의 시간 복잡도는 O(4^m x n x m)입니다. m(이모티콘 개수)이 최대 7개이고, n(사용자의 수)가 최대 100이기에 최악의 경우에는 약 1천만 개의 경우의 수를 탐색해야 합니다. 시간제한이 주어지진 않았지만, 1초 이내이기에 안전한 풀이라고 볼 수 있겠습니다. 

 

---

🎯 풀이 피드백

• 시간 다소 오래 걸렸다. 백트랙킹, 조합, 순열 등 복습하자..
• 잊고 있었던 백트랙킹 구현을 꺼내는 게 어려웠지, 나머지에서는 큰 어려움이 없었다.