자바 - 프로그래머스 / 이모티콘 할인 행사

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

프로그래머스

LV 2

 

구현 방법

1 ≤ emoticons의 길이 = m ≤ 7 이고, 할인 종류는 10, 20, 30, 40으로 4가지 경우가 있다.

따라서 각 이모티콘 마다 모든 할인 종류를 적용해봐도 4^7으로 런타임 에러 걱정은 없다. 

 

1. 이모티콘별 할인 가능한 모든 방법을 재귀 방식으로 구현한다. (중복 순열 개념이용)

2. 할인 가능한 한가지 순열이 나왔을 때,  우선순위가 있는 아래 조건에 따라 구현한다.

     2-1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
     2-2. 이모티콘 판매액을 최대한 늘리는 것.

 

코드

class Solution {
    
    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = {0, 0};
        
        int[] sales = {1, 2, 3, 4};
        int[] salesCase = new int[emoticons.length];
        
        //할인 중복 순열 구하기
        permutation(0, sales, salesCase, emoticons, users, answer);
       
        return answer;
    }
    
    private static void permutation(int cnt, int[] sales, int[] salesCase, int[] emoticons, int[][] users, int[] answer) {
        if (cnt == salesCase.length) {
            
            int[] tempAnswer = {0, 0};
            
            for (int i = 0; i < users.length; i++) {
                int tempPrice = 0;
            
                for (int j = 0; j < emoticons.length; j++) {
                    if ( salesCase[j] * 10 >= users[i][0] ) {
                        tempPrice += emoticons[j] - emoticons[j] * salesCase[j] / 10;
                    }
                }
            
                if (tempPrice >= users[i][1]) {
                    tempAnswer[0]++;
                } else {
                    tempAnswer[1] += tempPrice;
                }
            }
            
            if (tempAnswer[0] > answer[0]) {
                answer[0] = tempAnswer[0];
                answer[1] = tempAnswer[1];
            } else if (tempAnswer[0]  == answer[0]) {
                answer[1] = Math.max(tempAnswer[1], answer[1]);
            }
            
            return;
        }
        
        for(int i : sales) {
            salesCase[cnt] = i;
            permutation(cnt+1, sales, salesCase, emoticons, users, answer);
        }
    }
    
}

느낀 점

중복 순열을 재귀 함수로 구현하는 방법에 대해 배울 수 있었다.

코드의 재귀함수에서 파라미터로 넘겨주는 값이많은데, salesCase과 answer은 전역 변수로 빼두는 것이 더 좋아 보인다.

 

참고 블로그

https://sskl660.tistory.com/49

[Java]중복 순열(Permutation with repetition)