[프로그래머스 Lv.2] 이모티콘 할인행사(Java) - 완전탐색

📌 핵심 요약

• 완전탐색(DFS) — 이모티콘 하나당 10/20/30/40% 네 가지 할인율을 모두 대입한다. 최대 4⁷ = 16,384가지
• 판단 기준 — 구독자 수가 최우선, 같으면 판매액이 큰 쪽을 선택한다
• 겪은 오류 — new int[]{n}과 new int[n]을 혼동해 길이 1짜리 배열을 넘겼다
• 구조 문제 — 정답 후보를 static 필드에 두면 테스트케이스 간 상태가 남는다

 

목차

1 문제 정리

Programmers #150368

이모티콘 할인행사

users ≤ 100 · emoticons ≤ 7

난이도: Lv.2

각 이모티콘에 10, 20, 30, 40% 중 하나의 할인율을 정한다. 사용자는 자신의 기준 할인율 이상으로 할인되는 이모티콘을 전부 구매하고, 그 총액이 자신의 기준 금액 이상이 되면 구매를 취소하고 이모티콘 플러스 서비스에 가입한다.

목표

1. 이모티콘 플러스 가입자 수를 최대로 만든다.
2. 가입자 수가 같다면 이모티콘 판매액을 최대로 만든다.

완전탐색으로 접근한 이유

할인율의 선택지가 4가지로 고정되어 있고 이모티콘 개수가 최대 7개다. 가능한 할인율 조합은 4⁷ = 16,384가지에 불과하다. 여기에 조합마다 사용자 100명 × 이모티콘 7개를 훑어도 16,384 × 700 ≈ 1,147만 번이다. 시간 안에 충분히 들어오므로 모든 조합을 만들어 보는 방식으로 방향을 잡았다.

ℹ️

"최적해를 고를 근거가 없다"는 신호

할인율을 높이면 가입자는 늘지만 판매액은 줄고, 낮추면 반대가 된다. 어느 쪽이 유리한지 미리 판단할 규칙이 보이지 않는다. 이럴 때 입력 범위가 작다면 완전탐색이 정답인 경우가 많다.

2 처음 작성한 코드에서 발견한 문제

배열 초기화 실수

DFS를 호출하는 첫 줄에서 다음과 같이 배열을 넘겼다.

 

Java — 잘못된 배열 생성

dfs(users, emoticons, 0, new int[]{emoticons.length});

의도는 "이모티콘 개수만큼의 빈 배열"이었지만, 실제로 만들어진 것은 길이가 1이고 값이 emoticons.length인 배열이다. {}가 붙는 순간 크기 지정이 아니라 원소 나열로 해석되기 때문이다.

표현식	의미	length	내용
new int[3]	크기 3인 배열 생성	3	{0, 0, 0}
new int[]{3}	원소가 3 하나인 배열	1	{3}

그 결과 currentDiscounts[depth]에서 depth가 1이 되는 순간 ArrayIndexOutOfBoundsException이 발생한다. 이모티콘이 2개 이상인 모든 케이스가 여기서 멈춘다.

🚨

컴파일은 통과한다

new int[]{emoticons.length}는 문법적으로 완전히 올바른 코드다. 타입도 int[]로 맞기 때문에 IDE도 경고를 주지 않는다. 실행해야만 드러나는 종류의 실수다.

static 필드에 답을 저장한 구조

 

Java — 상태가 남는 필드

static int maxSub = 0;
static int maxMoney = 0;

static 필드는 클래스에 한 번만 만들어진다. 채점기가 하나의 클래스로 여러 테스트케이스를 연속 실행하면 이전 케이스에서 갱신된 maxSub가 그대로 남는다. 다음 케이스의 정답이 더 작은 값이라면 if (sub > maxSub) 조건이 영영 참이 되지 않아 오답이 된다.

이번 문제에서는 운 좋게 통과할 수도 있지만, 원인을 찾기 어려운 종류의 버그이므로 인스턴스 필드로 바꾸고 solution 진입 시 초기화하는 방식으로 정리했다.

💡

static을 써도 되는 것

countRate처럼 절대 바뀌지 않는 상수는 static final이 오히려 자연스럽다. 문제가 되는 것은 실행 중 값이 갱신되는 필드다.

3 수정한 전체 코드

 

Java — Solution.java

import java.util.*;

class Solution {
    static final int[] countRate = {10, 20, 30, 40};
    private int maxSub;
    private int maxMoney;

    public int[] solution(int[][] users, int[] emoticons) {
        maxSub = 0;
        maxMoney = 0;

        dfs(users, emoticons, 0, new int[emoticons.length]);

        return new int[]{maxSub, maxMoney};
    }

    private void dfs(int[][] users, int[] emoticons, int depth, int[] currentDiscounts) {

        // 다 채우면 계산
        if (depth == emoticons.length) {
            cal(currentDiscounts, users, emoticons);
            return;
        }

        // 할인율들을 채운다
        for (int rate : countRate) {
            currentDiscounts[depth] = rate;
            dfs(users, emoticons, depth + 1, currentDiscounts);
        }
    }

    private void cal(int[] currentDiscounts, int[][] users, int[] emoticons) {
        int sub = 0;   // 구독자
        int money = 0; // 이모티콘 판매액

        for (int i = 0; i < users.length; i++) {
            int purRate = users[i][0];  // 고객의 기준 할인율
            int purMoney = users[i][1]; // 고객의 기준 금액
            int totalMoney = 0;

            for (int j = 0; j < emoticons.length; j++) {
                int emRate = currentDiscounts[j]; // 할인율
                int emoticonMoney = emoticons[j]; // 이모티콘 가격

                // 할인율이 기준 이상일 때만 구매
                if (emRate >= purRate) {
                    totalMoney += emoticonMoney * (100 - emRate) / 100;
                }
            }

            if (totalMoney >= purMoney) {
                sub++;
            } else {
                money += totalMoney;
            }
        }

        if (sub > maxSub) {
            maxSub = sub;
            maxMoney = money;
        } else if (sub == maxSub) {
            maxMoney = Math.max(maxMoney, money);
        }
    }
}

4 짚고 넘어간 부분

배열을 되돌리지 않아도 되는 이유

백트래킹에서는 보통 재귀에서 돌아온 뒤 값을 원상복구한다. 그러나 이 코드는 currentDiscounts[depth] = rate로 같은 자리를 매번 덮어쓰는 구조다. 어떤 depth에 도달했을 때 0부터 depth-1까지는 이미 확정된 값이고, depth 이후의 값은 다음 재귀에서 다시 채워진다. 그래서 되돌리는 작업이 필요 없다.

정수 나눗셈 손실

emoticonMoney * (100 - emRate) / 100은 정수 연산이라 소수점이 버려질 수 있다. 다만 문제 조건에서 이모티콘 가격이 100의 배수라고 명시되어 있어 나머지가 발생하지 않는다. 조건을 확인하지 않았다면 실수형으로 처리하거나 계산 순서를 다시 봐야 했을 부분이다.

비교 순서

가입자 수를 먼저 비교하고, 동률일 때만 판매액을 비교한다. else if로 묶어야 하는 이유는 sub > maxSub인 순간 maxSub가 갱신되므로, 조건을 두 개의 독립된 if로 쓰면 곧바로 두 번째 조건도 참이 되어 의도가 어긋나기 때문이다.

⚠️

갱신 순서 주의

maxSub를 먼저 바꾸고 나서 같은 스코프에서 다시 sub == maxSub를 검사하면 언제나 참이다. 조건 분기는 갱신 전 상태를 기준으로 판단해야 한다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.