문제

문제 보러가기

풀이

아이디어

• 우선 모든 이모티콘에 대해 모든 할인율에 대한 순열을 구하는 게 맞다. (하..)
• 순열 구하는 함수만 짜면 나머지는 조건 비교 및 정렬이라서 비교적 쉽다.
• 순열을 구할 때는 DFS를 이용하였다.
  • emoticon을 하나하나 순회하면서 각 이모티콘에 대해서 할인율 총 4개에 대해서도 순회하면서 DFS로 넘겨주었다.
  • emoticon 인덱스가 마지막에 다다르면 모든 순열을 저장하고 있는 배열에 push해준다.
• 순열이 저장되어 있는 배열을 순회하면서 다음 로직을 수행한다.
  • 순열 원소 하나에 대해서 모든 사람을 순회하면서 각 사람의 할인율 기준 및 총 지출 기준을 체크하면서 이 사람을 이모티콘플러스 구독자로 넣어줄지, 아니면 모두 지불하고 사는 사람인지를 판단한다.
  • 판단 결과를 정답의 후보 배열(candidates)로 push해준다.
• candidates 배열을 1차적으로 이모티콘플러스 구독자 수 기준으로 내림차순 정렬하고, 2차적으로 총 판매수익을 기준으로 내림차순 정렬한다. 그렇게 했을 때 첫 번째 원소를 리턴하면 된다.

코드

function solution(users, emoticons) {
    const candidates = [];
    const percentage = [10, 20, 30, 40];
    const salePermutation = [];
    getSalePermutation(0, []);
    
    function getSalePermutation(emoIdx, tempPerm) {
        if(emoIdx == emoticons.length) {
            salePermutation.push(tempPerm);
            return;
        }
        for(let i=0; i<4; i++) {
            getSalePermutation(emoIdx+1, tempPerm.concat(percentage[i]));
        }
    }
    
    salePermutation.forEach(perm => {
        let priceSum = 0, subscriber = 0;
        users.forEach(user => {
            let toBuy = [];
            perm.forEach((p, i) => {if(p >= user[0]) toBuy.push(i)});
            let userSum = 0;
            toBuy.forEach(b => userSum += emoticons[b] * (1 - perm[b] / 100));
            if(userSum >= user[1]) subscriber++;
            else priceSum += userSum;
        });
        candidates.push([subscriber, priceSum]);
    });
    
    candidates.sort((a, b) => b[0] == a[0] ? b[1] - a[1] : b[0] - a[0])
    return candidates[0];
}

돌아보기

DFS로 순열을 만드니 코드 길이도 그렇고 생각보다 어렵지 않았던 건데 겁을 먹었다. 다음에 순열을 구할 일이 있다면 차근차근 DFS를 설계해보자.