본문 바로가기
코딩테스트/프로그래머스

[프로그래머스] 이모티콘 할인행사 풀이 및 코드 분석

by 현걸 2025. 3. 20.

문제 링크


1. 문제 분석

📌 문제 개요

  • 각 이모티콘에 대해 할인율(10%, 20%, 30%, 40%)을 결정해야 함
  • 모든 사용자가 특정 할인율 이상의 이모티콘을 구매하며, 특정 금액 이상 사용하면 이모티콘 플러스에 가입
  • 목표:
    1. 이모티콘 플러스 가입자를 최대로 늘리기
    2. 이모티콘 판매 수익을 최대로 늘리기

2. 해결 방법

🔹 완전 탐색 (백트래킹)

  • 이모티콘 개수 E가 최대 7개로 적기 때문에, 4^E(= 4^7 = 16384) 경우의 수를 탐색해도 무리가 없음.
  • 각 이모티콘이 가질 수 있는 할인율 (10%, 20%, 30%, 40%) 중 하나를 선택하는 모든 경우의 수를 확인
  • 백트래킹을 사용하여 가지치기하면서 탐색 진행

3. 코드 구현 (Java)

class Solution {

    static int U, E;

    static int[] price, answer;

    static int[] discount = {40, 30, 20, 10};

    public int[] solution(int[][] users, int[] emoticons) {
        answer = new int[2];

        U = users.length;
        E = emoticons.length;

        price = new int[U];

        comb(0, users, emoticons);

        return answer;
    }

    public void comb(int d, int[][] users, int[] emoticons) {
        if(d == E) {
            int sum = 0, cnt = 0;
            for(int i=0; i<U; i++) {
                if (price[i] >= users[i][1]) cnt++;
                else sum += price[i];
            }

            if(answer[0] < cnt) {
                answer[0] = cnt;
                answer[1] = sum;
            } else if (answer[0] == cnt) {
                answer[1] = Math.max(answer[1], sum);
            }

            return;
        }

        for(int i = 0; i < 4; i++) {
            int p = emoticons[d] * (100 - discount[i]) / 100;

            for(int u = 0; u < U; u++) {
                if(users[u][0] <= discount[i])
                    price[u] += p;
            }

            comb(d+1, users, emoticons);

            for(int u = 0; u < U; u++) {
                if(users[u][0] <= discount[i])
                    price[u] -= p;
            }
        }
    }
}

4. 코드 분석

🔹 주요 알고리즘

  1. 할인율을 4가지 중 하나로 선택 (완전 탐색)
    • 각 이모티콘마다 4가지 할인율(10%, 20%, 30%, 40%) 중 하나를 선택
    • 백트래킹 (재귀 호출)으로 모든 경우 탐색
  2. 사용자별 구매 비용 계산
    • 사용자의 할인 기준 이상이면 구매
    • 구매 비용이 특정 금액 이상이면 이모티콘 플러스 가입
  3. 가입자 수와 판매 수익 비교
    • 가입자가 많은 경우 최우선
    • 가입자가 같다면 판매 수익이 높은 경우 선택

5. 시간 복잡도 분석

  • E <= 7
    • 가능한 할인율 경우의 수 = 4^E (4^7 = 16384)
    • 각 경우마다 사용자 수 U = 100에 대해 계산 →O(U * E * 4^E)`
    • 최악의 경우 163만 번 연산충분히 해결 가능

6. 개선할 점 및 대체 방법

  • 비트마스킹을 사용해 할인율 조합을 생성하는 방식도 가능