[프로그래머스] Lv.02 이모티콘 할인행사 (JavaScript)

문제

프로그래머스

 

문제 설명

카카오톡에서 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리고자 한다고 합니다. 이를 위해 행사를 하는데 목표는 다음과 같다고 합니다.

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

1번 목표가 우선이며, 2번 목표가 그다음이라고 합니다.

이모티콘 할인 행사는 다음과 같은 방식으로 진행된다고 합니다.

• n 명의 카카오톡 사용자들에게 이모티콘 m 개를 할인하여 판매합니다.
• 이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.

카카오톡 사용자들은 다음과 같은 기준을 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매한다고 합니다.

• 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.
• 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.

카카오톡 사용자 n 명의 구매 기준을 담은 2차원 정수 배열 users, 이모티콘 m 개의 정가를 담은 1차원 정수 배열 emoticons가 주어졌을 때, 행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 반환하면 되는 문제입니다.

 

※제한사항

• 1 <= users의 길이 = n <= 100
  • users의 원소는 [비율, 가격]의 형태입니다.
  • users[i]는 i+1번 고객의 구매 기준을 의미합니다.
  • 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
    • 1 <= 비율 <= 40
  • 가격 이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
    • 100 <= 가격 <= 1,000,000
    • 가격은 100의 배수입니다.
  • 1 <= emoticons의 길이 = m <= 7
    • emoticons[i]는 i+1번 이모티콘의 정가를 의미합니다.
    • 100 <= emoticons의 원소 <= 1,000,000
    • emoticons의 원소는 100의 배수입니다.

 

풀이

주어진 이모티콘에서 가능한 모든 할인 조합을 확인하기 위해 dfs를 이용하여 접근하였습니다.

40%부터 시작해서 10%까지 반복을 진행하며 할인율을 설정해 주고 그에 따른 조합을 계산하였습니다.

const dfs=(depth) => {
        if(depth === emoticons.length){
            price();
            return true;
        }
        
        for(let i=40;i>=10;i-=10){
            info[depth] = i;
            dfs(depth+1);
        }
    }

 

그다음으로 이모티콘 플러스 가입자를 판별하고 그에 따른 판매액을 계산하기 위해 price라는 함수를 만들어주었습니다.

const price=() => {
        let result = [0,0]
        
        users.map((user) => {
            let total = 0;
            emoticons.map((emoticon,idx) => {
                if(user[0] <= info[idx]){                                
                    total += (emoticon - (emoticon * info[idx]/100))
                }
            })
            if(total >= user[1]){
                total = 0;
                result[0]+=1
            }else {
                result[1]+=total
            }
            
            if(answer[0]<result[0] || (answer[0] === result[0] && answer[1] < result[1])){
                answer=[...result]
            }
        })
    }

 

아래는 전체 코드입니다.

function solution(users, emoticons) {
    var answer = [0, 0];
    let info = []; // 각 이모티콘에 적용할 할인율을 저장할 배열

    // 현재 할인율 조합에 따라 가격을 계산하는 함수
    const price = () => {
        let result = [0, 0]; // 현재 할인 조합에 대한 이모티콘 플러스 유저 수와 총 판매액 초기화
        
        users.map((user) => {
            let total = 0; // 현재 사용자의 총 판매액 초기화
            
            // 각 이모티콘 가격을 확인
            emoticons.map((emoticon, idx) => {
                // 사용자가 수용할 수 있는 할인율보다 현재 할인율이 크거나 같으면
                // 할인된 가격을 계산하여 total에 추가
                if (user[0] <= info[idx]) {
                    total += (emoticon - (emoticon * info[idx] / 100));
                }
            });
            
            // 총 판매액이 사용자의 최소 지출 금액을 충족하는지 확인
            if (total >= user[1]) {
                total = 0; // 이모티콘 플러스 유저이므로 0으로 리셋
                result[0] += 1; // 유저 수 증가
            } else {
                result[1] += total; // 총 판매액에 total 추가
            }
            
            // 현재 결과가 기존의 최대값을 초과하는지 확인
            if (answer[0] < result[0] || (answer[0] === result[0] && answer[1] < result[1])) {
                answer = [...result]; // 최대값 업데이트
            }
        });
    }

    const dfs = (depth) => {
        // 모든 이모티콘에 대해 할인율을 설정했으면 가격 계산
        if (depth === emoticons.length) {
            price(); // 현재 할인율 조합에 따라 가격 계산
            return true; // 종료
        }
        
        // 40%에서 10%까지의 할인율을 설정하여 DFS 호출
        for (let i = 40; i >= 10; i -= 10) {
            info[depth] = i; // 현재 깊이에 해당하는 할인율 설정
            dfs(depth + 1); // 다음 깊이로 DFS 진행
        }
    }

    dfs(0); // DFS 시작

    return answer; // 최대 구독자 수와 총 판매액 반환
}