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

📙 1. 문제

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

문제 설명

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

이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
이모티콘 판매액을 최대한 늘리는 것.
1번 목표가 우선이며, 2번 목표가 그 다음입니다.

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

n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매합니다.
이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.
카카오톡 사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입합니다.

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

제한 사항

• 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 1

const rates = {
    0.9:10,
    0.8:20,
    0.7:30,
    0.6:40,
}

function solution(users, emoticons) {

    const arr = [];
    let [maxUser,maxPrice] = [0,0];
    
    const dfs = () => {
        if(arr.length===emoticons.length){
            let [sumPrice,sumUser]=[0,0]
            users.forEach(user=>{
                let [minPercent, maxPrice] = user;
                let sum = arr.reduce((prev,cur,i)=>rates[cur]>=minPercent ? prev+cur*emoticons[i] : prev,0)
                sum>=maxPrice?sumUser++:sumPrice+=sum
            })
            if(maxUser<sumUser) {
                maxUser=sumUser
                maxPrice=sumPrice
            }else if(maxUser===sumUser && maxPrice<sumPrice){
                maxPrice=sumPrice
            }
            return;
        }
        Object.keys(rates).forEach(rate=>{
            arr.push(rate)
            dfs()
            arr.pop()
        })
    }
    dfs()
    return[maxUser,maxPrice]
}

1. emoticons의 각 요소에 0.9/0.8/0.7/0.6 중 하나를 곱한다
2. users를 순회하며 users[0]가 할인율 이상인 값만 더함 -> 더한 값이 users[1]이상이라면 플러스 구매자. 아니라면 이모티콘 구매자
3. emoticons최대 길이 = 7. 시간복잡도 O(4^m^n)(m최대 7, n최대 100) -> 노가다 할 경우 최대 160만

• DFS(깊이 우선 탐색)을 이용하여 모든 만들 수 있는 할인율의 경우의 수를 탐색한다. 
• arr배열에는 할인율을 emoticons수를 넣는다. users.forEach문을 이용하여 모든 users별로 각 할인율 경우 별 이모티콘 가격과 이모티콘 플러스 가입자 수를 계산한다.
• 이모티콘 플러스 가입자가 많다면 갱신을 하고, 가입자는 동일하지만 이모티콘 가격이 더 높다면 또 갱신한다.

 

다른 사람 풀이 : DFS

function solution(users, emoticons) {
    let discount = [10, 20, 30, 40];
    let len = emoticons.length;
    let res = [];
    let arr = Array(len).fill(0);

    const dfs = (depth) => {
        if (depth === len) {
            res.push(arr.slice());
            return;
        }

        for (let i = 0; i < 4; i++) {
            arr[depth] = discount[i];
            dfs(depth + 1);
            arr[depth] = 0;
        }
    };

    dfs(0);

    let pp = 0, c = 0;

    for (let i = 0; i < res.length; i++) {
        let sales = res[i];
        let counter = 0, money = 0;

        for (let j = 0; j < users.length; j++) {
            let [a, b] = users[j];
            let sum = 0;
            let flag = false;

            for (let k = 0; k < len; k++) {
                if (sales[k] >= a) {
                    sum += emoticons[k] * (100 - sales[k]) / 100;
                }
                if (sum >= b) {
                    flag = true;
                    break;
                } 
            }

            if (flag) counter++;
            else money += sum;
        }

        if (counter > pp) {
            pp = counter, c = money;
        } else if (counter === pp && money > c) c = money
    }

    return [pp, c];

    // console.log('res: ', res, res.length);
}

• 할인율을 굳이 hash함수를 사용하지 않고, 배열로 만들었다.
• dfs 안에서 연산하는 것이 아닌, res에 모든 결과물을 하나씩 축적한 후, dfs가 완전히 종료된 후 for문을 이용하여 남은 계산을 해주었다.

---

🤔 2. 느낀 점

• DFS로 모든 경우의 수를 탐색할 경우 시간 복잡도가 4^m^n이라 '이게 아닌가'싶었지만, 다른 방법이 도저히 생각나지 않아서 결국 DFS로 풀었다. 다 풀고 제출 했을 때 하나하나씩 테스트를 통과할 때 기분은 아주 짜릿했다.
• 오늘도 Lv2의 32%정답률을 풀었다. 시간은 50분 정도 소요되었다. 시간이 아무리 오래 걸리더라도, 앞으로도 오늘처럼 계속 고민해보자. 결국엔 풀리는구나. 시간 줄이는 것은 차차 해나가면 된다. 문제를 많이 풀다보면 자연스레 줄어들 것이다.

 

🤩 3. 한 번 더 짚고 갈 점

• 정말 모든 경우의 수를 탐색해야 한다 -> DFS를 과감히 이용할 것