[JS] 이모티콘 할인 행사

DP나 조금 색다른 방법으로 풀기위해 고민하다가 오히려 시간을 엄청 뺏긴 문제였다..

 

항상 문제를 풀때는 테스트 케이스를 볼 필요가 있을 것 같다. 이모티콘의 개수는 7개, 할인의 개수는 4개이므로

 

4^7 ====> 2의 14승 즉,  모든 경우의 수를 단순하게 찾아보려고 해도 약 16000개정도의 테스트 케이스만 나왔다.

 

그 중 사람들이 이모티콘을 살 수 있는지 없는지는 최대 100 * 7 정도의 연산이 필요하니..

 

아무리 테케를 크게 잡아도 크게 시간초과가 날만한 문제가 아니었다.

 

 

 

 

DFS로 구현을 해볼까 중복조합으로 해결해볼까 고민하다가 이참에 조금 더 깔끔한 로직을 위해서 중복조합 구하는 함수도 복습할겸 이를 써봐서 구현해보았다.

 

 

 

function solution(users, emoticons) {
    const dcList = [10,20,30,40]
    
    const getPermutation = (ary , n) => {
        let ret = []
        if (n===1) return ary.map(v =>[v])
        
        ary.forEach((v,idx,ary) => {
            const fixed = v
            const rest = ary
            const permutation = getPermutation(rest,n-1)
            const combineFix = permutation.map(v => [fixed , ...v])
            ret.push(...combineFix)
        })
        return ret
    }
    
    let ret = [0,0]
    for (const dc of getPermutation(dcList,emoticons.length)){
        let plus = 0
        let totalMoney = 0
        for (const [percent,money] of users){
            let sum_ = 0
            for (let i = 0 ; i < dc.length ; i++) {
                if (percent <= dc[i]) sum_ += emoticons[i] * (100-dc[i]) / 100
            }
            if (sum_ >= money) plus ++
            else totalMoney += sum_
        }
        
        
        if (plus > ret[0] || (plus===ret[0] && totalMoney > ret[1])) ret = [plus,totalMoney]
    }
    
    return ret
}