[프로그래머스 LV2] 이모티콘 할인행사 JS

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

프로그래머스

---

 

문제요점

• 가입자 최대, 판매액 최대
• n명에게 m개를 할인판매
• 이모티콘마다 할인율은 10%, 20%, 30%, 40%
• 기대이상 할인하는 이모티콘모두 구매
• 구매비용 합이 일정가격 이상이면 구매를 모두 취소하고 서비스 가입
• 목적 최대달성한 [가입자수, 매출액]

생각

• 유저 최대 100명, 이모티콘 최대7개
• 정해진 조합: 7개 이모티콘의 할인율 조합갯수 = 4^7 = 16384
• 유저마다 각 이모지를 구매하는 가격추가
• 전부 다 가입하면 안됌? => 그렇게 할 수 없는 경우 존재 => 따지지 말구 완전탐색 후 정렬이 정확

문제풀이

처음에 문제 이해하는데 시간이 많이 걸렸다

주어진 예를 천천히 보며 노트에 그려보니 대략적으로 정리가 됐다.

요점은 dfs + 완전탐색을 통해 
할인율조합 기준으로 최대 서비스 && 최대 판매량을 탐색하는거였다

 

 

• 일단 이모티콘을 사게 만들어야한다 => 할인율이 유저의 최소기대할인율 이상여야한다 => 최소기대할인율을 찾아서 discount에서 배제한다.
• 이모티콘을 하나씩 사면서 모두 살 때까지 dfs(이모티콘을 산 횟수, 비용배열)를 탐색한다.
  
  • 가능한 할인율을 순회한다
  • 할인율을 정한 뒤에 유저를 순회해 유저가 쓴 돈을 갱신한다 (for discount 내부에 for user)
  • 이 때 할인율이 유저의 기대 할인율 이상이면 돈을 쓴다
  • [dfs 탈출조건] 이모티콘을 사는 횟수 === 이모티콘 갯수로 끝에 다다렀을 때, 각 경우의 [서비스 갯수, 돈 총합]을 answer배열에 넣고 dfs를 끝낸다
• 모든 이모지를 사면 유저마다 쓴 돈과 보유한 돈을 비교하여 해당 할인조합의 [서비스수, 판매량]을 answer에 저장한다.
• 모든 할인조합을 구한 뒤 서비스수가 큰 순으로, 같다면 판매량 큰 순으로 정렬한다

 

 

 

전체코드

function solution(users, emoticons) {
    var answer = [];
    let discounts = [10, 20, 30, 40];
    const minWishDiscount = users.sort((a, b) => a[0] - b[0])[0][0]; // 모든 유저의 최소기대할인율
    discounts = discounts.filter(d => d >= minWishDiscount); // 이모티콘 할인율은 유저의 최소 기대할인율보다 커야함 (최소 20%이상인데, 이모티콘이 10%할인하면 구매자없음)
    const cost = Array.from({length: users.length}, () => 0); // 사용자마다 총구매가격
    
    function buyEmoji(currEmoji, cost) {
        // [탈출 조건] 이모지를 다 사면 끝
        if (currEmoji === emoticons.length) {
            let service = 0;
            let earnMoney = 0;
            // 사용자마다 현재 이모티콘 구매여부 결정
            for (let i = 0; i < users.length; i++) {
                const money = users[i][1];
                // 보유한 돈 이상을 소비해야하면 구매를 취소하고 서비스가입
                if (cost[i] >= money) {
                    service++;
                } else {
                    earnMoney += cost[i]; // 초과하지 않으면 그냥 구매
                }
            }
            answer.push([service, earnMoney]);
            return;
        }
        const currEmojiPrice = emoticons[currEmoji];
        // 각 할인율마다 유저의 현재이모티콘 구매여부 갱신
        for (const d of discounts) {
            const newCost = [...cost];
            
            for (let i = 0; i < users.length; i++) {
                const [wishDiscount, money] = users[i];
                // 현재할인율이 기대할인율보다 크거나 같으면 구매
                if (d >= wishDiscount) {
                    newCost[i] += currEmojiPrice * (100 - d) /100;
                }
            }
            buyEmoji(currEmoji+1, newCost);
        }
    }
    buyEmoji(0, cost); // 첫번째 이모티콘부터 구매
    
    // 가입자수 최대로, 가입자수가 같으면 판매액 최대로 정렬
    return answer.sort((a, b) => {
            // 가입자 수가 같을 때
            if (a[0] === b[0]) {
                return b[1] - a[1];
            }
            return b[0] - a[0];
        })[0];
}

 

 

 

느낀 점

• 문제를 이해하는데 시간이 오래걸렸다. 할인율이 4가지라서 조합을 떠올리긴 했는데 할인율, 유저, 이모티콘의 조합을 어떻게 풀어낼지에서 막혀서 힌트를 봤다.
• 보고 나서 시간이 오래걸렸지만 스스로 풀 수 있어서 좋았다. 다음엔 혼자 힘으로 풀어보겠다.
• 생각이 복잡할 때는 문제묘사 그대로 로직을 적는게 훨씬 간편하고 도움이 된다

배운 점

• 유한한 조합 => 완전탐색 => dfs로도 가능
• 이모티콘, 할인율, 유저 고려할게 많을때
• => 유저, 이모티콘은 고정된 값이고 내가 조절할 수 있는 건 할인율
• => 할인율 기준으로 가지치기 (종료는 이모티콘, 유저로 판단)