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

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

프로그래머스

문제 풀이

순열을 이용하여 각 상품의 적용할 수 있는 할인율을 모두 구하여 완전 탐색을 통해 원하는 결과를 얻을 수 있다.

할인율 4개, 이모티콘 갯수 최대 7개로 순열의 경우의 수는 4^7로 16384개가 나오고 이렇게 나온 모든 경우의 수에 대하여 각 유저가 구매할 수 있는지 체크해야 하므로 최대 유저 100명이니까 1,678,400의 연산이 수행된다. 비교적 적은 횟수로 완전 탐색을 진행하여도 시간초과는 발생하지 않을 것이다.

 

 

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
    static int[] discounts = {10, 20, 30, 40};
    static List<int[]> permutations;
    static int[] permutation;

    public int[] solution(int[][] users, int[] emoticons) {
        int answer[] = {0, 0};
        permutations = new ArrayList<>();
        permutation = new int[emoticons.length];
        getPermutations(0, emoticons.length);

        // 완전 탐색
        for (int i = 0; i < permutations.size(); i++) {
            permutation = permutations.get(i);
            int subscribePlusCnt = 0;
            int sellPrice = 0;

            for (int j = 0; j < users.length; j++) {
                int total = 0;
                for (int k = 0; k < permutation.length; k++) {
                    if (users[j][0] <= permutation[k]) {
                        total += emoticons[k] * (100 - permutation[k]) / 100;
                    }

                    // 구매액을 넘겼으면 가입
                    if (users[j][1] <= total) {
                        total = 0;
                        subscribePlusCnt++;
                        break;
                    }
                }
                sellPrice += total;
            }

            // answer의 값과 비교하여 최댓값 추가
            if (answer[0] < subscribePlusCnt) {
                answer[0] = subscribePlusCnt;
                answer[1] = sellPrice;
            } else if (answer[0] == subscribePlusCnt) {
                if (answer[1] < sellPrice) {
                    answer[0] = subscribePlusCnt;
                    answer[1] = sellPrice;
                }
            }
        }

        return answer;
    }

    static void getPermutations(int idx, int len) {
        if (idx == len) {
            permutations.add(permutation.clone());
            return;
        }

        for (int discount : discounts) {
            permutation[idx] = discount;
            getPermutations(idx + 1, len);
        }
    }
}