(프로그래머스 KAKAO JS)이모티콘 할인행사

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

프로그래머스

DFS를 이용한 문제 풀이.

 

우선 answer에 -Infinity 2개를 넣어주어서 최대값 갱신을 할 수 있도록 한다.

이모티콘 할인율은 10, 20, 30, 40 4개가 있으므로 discounts 배열에 저장.

users와 emoticons의 길이를 나타내는 변수 usersLength, emoticonsLength.

각 유저가 이모티콘을 구매했을 때의 비용을 나타내는 userCost를 선언한다.

 

getCost() 함수는 이모티콘을 할인율에 따라 구매했을 때의 비용을 리턴해준다.

 

dfs() 함수는 어느 이모티콘을 기점으로 탐색할 지 알 수 있는 startIndex만 받아오면 된다.

 

리턴 조건을 먼저 정해준다.

startIndex == emoticonsLength

현재 인덱스가 emoticons의 길이와 같다면 더 이상 진행할 수 없다.

여기서 최대 가입자수와 최대 매출액인지 확인해서 갱신해주면 된다.

먼저 userCost에 저장되어 있는 값과 user의 조건에 해당하는지 for문으로 검사하여 가입자 수와 매출액을 계산한다.

계산이 끝나면 현재 가입자 수가 answer[0]보다 크거나, 현재 가입자 수가 answer[0]과 같지만 현재 매출액이 answer[1]보다 크다면 answer를 갱신해주고, 리턴하면 된다.

 

함수 종료조건에 맞지 않는다면 dfs를 진행한다.

for문으로 현재 이모티콘의 할인율에 따라 userCost를 계산한다.

할인율은 user의 조건에 부합할 때만 계산해주면 된다.

 

현재 할인율에 대한 계산이 끝났다면 다음 이모티콘을 구매하는 dfs를 진행한다.

위 dfs가 끝났다면 다시 현재 할인율의 cost를 다시 되돌리고(백트랙킹) 현재 이모티콘에서 다음 할인율을 계산하는 방식으로 dfs를 진행하면 답이 도출된다.

function solution(users, emoticons) {
    const answer = [-Infinity, -Infinity];
    const discounts = [40, 30, 20, 10];
    const usersLength = users.length;
    const emoticonsLength = emoticons.length;
    const userCost = Array.from({length: usersLength}, () => 0);
    
    const getCost = (index, rate) => {
        return emoticons[index] * (100 - rate) / 100;
    }
    
    const dfs = (startIndex) => {
        if(startIndex == emoticonsLength) {
            let maxRegister = 0;
            let maxCost = 0;
            
            for(let i = 0; i < usersLength; i++) {
                if(userCost[i] >= users[i][1]) {
                    maxRegister++;
                } else{
                    maxCost += userCost[i];
                }
            }
            
            if((maxRegister > answer[0]) || (maxRegister == answer[0] && maxCost >= answer[1])) {
                answer[0] = maxRegister;
                answer[1] = maxCost;
            }
            
            return;
        }
        
        for(let i = 0; i < 4; i++) {
            const discountRate = discounts[i];
            
            for(let j = 0; j < usersLength; j++) {
                if(users[j][0] <= discountRate) {
                    userCost[j] += getCost(startIndex, discountRate);
                }
            }
            
            dfs(startIndex + 1, answer[0], answer[1]);
            
            for(let j = 0; j < usersLength; j++) {
                if(users[j][0] <= discountRate) {
                    userCost[j] -= getCost(startIndex, discountRate);
                }
            }
        }
    }
    
    dfs(0);

    return answer;
}