99클럽 코테 스터디 28일차 TIL [조합]

 

- 오늘의 학습 키워드 : 조합

[문제 이름 : 이모티콘 할인행사 (프로그래머스 2023 KAKAO 인턴, Lv 2)]
문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/150368

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    static int n, m;
    static int[] discounts = {10, 20, 30, 40};
    static int maxSubscribers = 0;
    static int maxSales = 0;

    public int[] solution(int[][] users, int[] emoticons) {
        n = users.length;
        m = emoticons.length;

        // 할인율 조합
        combi(emoticons, users, new int[m], 0);

        // 최적 결과 반환
        return new int[]{maxSubscribers, maxSales};
    }

    // 할인율 조합 생성
    private void combi(int[] emoticons, int[][] users, int[] curDiscounts, int depth) {
        if (depth == m) {
            // 모든 할인율 조합 저장 시 계산 구현
            simulate(users, emoticons, curDiscounts);
            return;
        }

        for (int discount : discounts) {
            curDiscounts[depth] = discount;
            combi(emoticons, users, curDiscounts, depth + 1);
        }
    }

    // 사용자 구매 및 서비스 가입 시뮬레이션
    private void simulate(int[][] users, int[] emoticons, int[] currentDiscounts) {
        int subscribers = 0;
        int totalSales = 0;

        for (int[] user : users) {
            int minDiscount = user[0];
            int priceThreshold = user[1];

            int userTotal = 0;

            // 이모티콘 구매 시뮬레이션
            for (int i = 0; i < m; i++) {
                if (currentDiscounts[i] >= minDiscount) {
                    userTotal += emoticons[i] * (100 - currentDiscounts[i]) / 100;
                }
            }

            // 기준 금액 초과 시 서비스 가입
            if (userTotal >= priceThreshold) {
                subscribers++;
            } else {
                totalSales += userTotal;
            }
        }

        // 결과 업데이트
        if (subscribers > maxSubscribers || (subscribers == maxSubscribers && totalSales > maxSales)) {
            maxSubscribers = subscribers;
            maxSales = totalSales;
        }
    }
}

풀이 과정(풀이 시간 : 1시간)

조합, 순열 문제가 미숙하여 연습이 필요했었는데, 이번 문제를 통해서 개념을 다시 복습할 수 있어서 너무 좋았다.

 

1. m개의 이모티콘에 해당하는 퍼센테이지를 저장할 수 있는 curDiscounts배열을 combi() 메서드에서 사용한다. 예를 들어, m=2개인 이모티콘이라면 다음과 같이 표현할 수 있다.

(10, 10), (10, 20), (10, 30), (10, 40),

(20, 10), (20, 20), (20, 30), (20, 40),

(30, 10), (30, 20), (30, 30), (30, 40),

(40, 10), (40, 20), (40, 30), (40, 40)

즉, 4의 m승 (4의 m제곱 만큼)의 경우의 수를 고려해보아야 한다. 이를 combi 함수에서 확인할 수 있다.

2. 아래와 같이 재귀함수를 돌려주면, 모든 조합의 경우의 수에 대해 판별할 수 있다. 이때 모든 조합의 경우의 수는 각 이모티콘 별 10%, 20%, 30%, 40%가 되는 경우의 수를 의미한다.

for (int discount : discounts) {
            curDiscounts[depth] = discount;
            combi(emoticons, users, curDiscounts, depth + 1);
        }

 

3. 각 이모티콘 별 할인율이 구해진다면, simulate() 함수로 최대 가입자 수 및 판매액을 판별해볼 수 있다. 기준 금액을 초과했을 때에는 서비스 가입자 수를 늘려주고, 아니라면 총 판매액 수를 계산해준다.
4. 이모티콘 플러스 서비스 가입자를 최대한 늘리고, 만약 같다면 판매액을 최대한 늘려야 하므로 이를 마지막에 계산해준다.

내일은 인공지능 AI 크리에이터 면접에 대비하여 예상 질문 및 관련 조사를 해보고자 한다.