[2023 KAKAO BLIND RECRUITMENT] 이모티콘 할인행사

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150368

[이 문제는 프로그래머스에서 푼 문제입니다.]
이 문제는 중복 순열을 이용한 완전 탐색방법으로 풀 수 있습니다. 이 문제는 언뜻 봤을 때 시간 초과가 날 수도 있겠다고 생각할 수 있습니다. 하지만 깊게 들여다보면 완전탐색으로 진행해도 시간 초과가 나지 않는다는 것을 알 수 있습니다.

이 문제는 이모티콘이 가질 수 있는 할인율이 4개이고, 이모티콘의 개수가 7개이기 때문에 모든 이모티콘의 할인율을 적용시킨 총 케이스의 수는 4^7, 즉 4개의 원소들 중에서 7개의 수를 뽑는 중복 순열과 같은 경우의 수입니다. 따라서 중복순열을 구현하여 모든 테스트 케이스를 구한 후 각 케이스 별 유저들의 값들을 기록하여 조건에 맞게 처리하면 됩니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    // 이모티콘 할인율 배열
    static int[] discounts = { 10, 20, 30, 40 };
    // 중복순열 결과 담을 임시 배열
    static int[] result = new int[7];
    // 이모티콘 총 경우의 수
    static int fin;
    // 이모티콘 별 모든 할인율 적용 케이스
    static ArrayList<int[]> res = new ArrayList<>();
    
    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = {0,0};
        // 유저 수
        int n = users.length;
        // 이모티콘 수
        int m = emoticons.length;
        
        // 이모티콘 총 경우의 수
        fin = (int) Math.pow(4,m);
        
        // result에 모든 경우의 수 중복 순열로 추가
        permutation_with_repetition(0, 4, m);
        
        // 모든 경우의 수에 따른 유저들의 최댓값 계산
        for(int i=0;i<fin;i++){
            int[] curr = res.get(i);
            int userNum = 0;
            int profitSum = 0;
            
            // 유저 별 케이스에서 구매액 계산
            for(int j=0;j<n;j++){
                int total = 0;
                
                for(int k=0;k<curr.length;k++){
                    // 구매 가능 비율이면 구매
                    if(users[j][0] <= curr[k]){
                        total += emoticons[k]*(100 - curr[k])/100;
                    }
                    
                    // 구매액을 넘겼으면 가입
                    if(users[j][1] <= total){
                        total = 0;
                        userNum++;
                        break;
                    }
                }
                
                // 수입 추가
                profitSum += total;
            }
            
            // answer의 값과 비교하여 최댓값 추가
            if(answer[0] < userNum){
                answer[0] = userNum;
                answer[1] = profitSum;
            }
            else if(answer[0] == userNum){
                if(answer[1] < profitSum){
                    answer[0] = userNum;
                    answer[1] = profitSum;
                }
            }
        }
        
        
        return answer;
    }
    
    private static void permutation_with_repetition(int cnt, int n, int r) {
        // r개를 선택했을 때 결과 배열에 지금까지 지나온 값들 저장
        if (cnt == r) {
            int[] tmp = result.clone();
            res.add(tmp);
            return;
        }
        // 중복순열이기 때문에 처음부터 탐색
        for (int i = 0; i < n; i++) {
            // 현재 cnt에 값 추가
            result[cnt] = discounts[i];
            // 이어서 재귀호출
            permutation_with_repetition(cnt + 1, n, r);
        }
    }
}