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

https://school.programmers.co.kr/learn/courses/30/lessons/150368

프로그래머스

 

문제 요약

이모티콘마다 할인율을 다르게 적용했을 때,

• 이모티콘 플러스 가입자 수를 최대화하고
• 가입자 수가 같다면 매출액을 최대로 만드는 할인 조합을 찾아야 한다.

각 유저는

• users[i][0] → 최소로 원하는 할인율
• users[i][1] → 이 금액 이상이면 플러스 가입

이모티콘은 emoticons[i]로 주어지며, 할인율은 10%, 20%, 30%, 40% 중 하나만 선택 가능하다.

 

접근 아이디어

1. 할인율 조합 완전탐색 (DFS)
   • 이모티콘의 개수가 최대 7개이므로
     가능한 경우의 수는 4^7 = 16,384 → 충분히 완전탐색 가능
2. 미리 할인 가격 계산
   • 매번 (가격 * (100 - 할인율) / 100) 계산하기엔 반복이 많으니,
     10%, 20%, 30%, 40% 할인된 가격을 미리 배열에 저장해둔다.
3. 유저별 구매 판단
   • 각 유저가 원하는 최소 할인율 이상인 이모티콘만 구매합산
   • 합계가 기준 금액(Uplus) 이상이면 플러스 가입
   • 아니면 구매 금액을 매출로 더함
4. 비교 조건
   • 플러스 가입자 수가 더 많으면 갱신
   • 같을 경우, 매출이 더 높은 경우로 갱신

 

import java.util.*;

class Solution {
    public static int[] arr;         
    public static int sales, plus;
    public static int Esize, Usize;
    public static int[][] cost, users;

    public int[] solution(int[][] users, int[] emoticons) {
        Esize = emoticons.length;
        Usize = users.length;
        sales = 0;
        plus = 0;
        cost = new int[5][Esize];
        arr = new int[Esize];
        this.users = users;
        
        // 할인율별 가격 미리 계산
        for(int i = 0; i <= 4; i++){
            for(int j = 0; j < Esize; j++){
                int cur = emoticons[j];
                cost[i][j] = cur - (cur / 100) * (i * 10);
            }
        }
        
        // 할인 조합 완전탐색 (중복순열)
        dfs(0);
        
        return new int[]{plus, sales};
    }

    public static void dfs(int depth){
        // 모든 이모티콘에 할인율이 지정된 경우 평가
        if(depth == Esize){
            int curPlus = 0;
            int curSales = 0;

            for(int i = 0; i < Usize; i++){
                int Udis = users[i][0]; // 유저가 원하는 최소 할인율
                int Uplus = users[i][1]; // 플러스 가입 기준 금액
                int sum = 0;

                for(int j = 0; j < Esize; j++){
                    int dis = arr[j];
                    if(dis * 10 >= Udis){ // 최소 할인율 이상이면 구매
                        sum += cost[dis][j];
                    }
                }

                if(sum >= Uplus) curPlus++; 
                else curSales += sum;
            }

            // 최대 가입자, 매출 갱신
            if(curPlus > plus){
                plus = curPlus;
                sales = curSales;
            } else if(curPlus == plus){
                sales = Math.max(curSales, sales);
            }
            return;
        }

        // 각 이모티콘에 대해 할인율 부여
        for(int i = 0; i <= 4; i++){
            arr[depth] = i;
            dfs(depth + 1);
        }
    }
}

 

복잡도 분석

구분계산식설명

할인 조합 수	4^E	이모티콘 개수 E
유저 평가	× U	각 조합마다 U명의 유저 평가
총 연산량	O(4^E × U)	최대 16,384 × 100 ≈ 1.6M → 충분히 가능

 

풀이 회고

• 처음엔 1~40% 전부 탐색(40^7) 하다보니 시간 초과와 논리 오류가 났다.
• 문제 조건을 다시 읽어보니 할인율은 {10, 20, 30, 40} 네 가지뿐이었다.
• 할인율 후보를 줄이니 코드가 훨씬 단순해지고 통과
• 완전탐색 문제는 "가능한 조합의 개수"를 먼저 계산해보는 습관을 들이자.