[JS] 이모티콘 할인행사

문제

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

프로그래머스

 

풀이

이 문제의 경우 문제를 잘못 이해해 시간을 까먹고 햇갈려했던 문제이다.... 내가 부족해서...

 

이 문제에서 입력되는 데이터의 양을 보고 시간복잡도를 생각하며 굉장히 널널하다는 것을 알 수 있다.

각 이모티콘별 적용되는 할인율이 다를 수 있기 때문에 각 할인율의 조합별로 인원이 구매할 것인지 멤버십에 가입할 것인지 판단하면 된다.

 

최종적으로는 멤버십이 판매액보다 중요시 되기 때문에 주의해야 한다.

 

DFS 알고리즘을 이용해 각 이모티콘별 적용되는 할인율의 조합을 구한다. 그 다음 조합별로 구매자가 이모티콘들을 구매할 것인지 아니면 멤버십에 가입할 것인지 확인한 뒤 각 결과를 종합한다. 마지막으로 종합된 결과를 최종적으로 제출할 결과와 비교해 최적의 답을 도출한다.

 

코드

function solution(users, emoticons) {
  let answer = [0, 0];
  const discounts = [10, 20, 30, 40];
  const arr = [];
    
  const dfs = (emos, res) => {
    if (emos.length === 0) {
      arr.push(res);
      return;
    }
    else {
      for (const discount of discounts) {
        dfs(emos.slice(1), [...res, discount]);
      }
    }
  }
  dfs(emoticons, []);
    
  for (const combi of arr) {
    let [plus, total] = [0, 0];
        
    for (const [minPer, maxValue] of users) {
      let cost = 0;
      let flag = false;
      for (let i = 0; i < combi.length; i++) {
        if (minPer > combi[i]) continue;
        cost += emoticons[i] - (emoticons[i] * (combi[i] / 100));
        if (cost >= maxValue) {
          flag = true;
          break;
        }
      }
      flag ? plus++ : total += cost;
    }
        
    if (plus > answer[0] || (plus === answer[0] && total > answer[1])) {
      answer = [plus, total];
    }
  }
    
  return answer;
}