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

코딩테스트 연습 - 이모티콘 할인행사 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

알고리즘 : 구현, dfs

 

dfs를 사용하는 방법이 생각보다 어렵다.

완전탐색을 통해 경우의 수를 정리하고 나머지는 구현문제

그래도 확실히 카카오 문제가 깔끔하고 문제의질이 좋다.

 

function solution(users, emoticons) {
      let n = users.length;
  let m = emoticons.length;

  let arr = [];
  let dis = [10, 20, 30, 40];

  // dfs -> 완전탐색
  const dfs = (emoticons, result) => {
    if (!emoticons.length) {
      arr.push(result);
      return;
    }
    for (let i = 0; i < dis.length; i++) {
      dfs(emoticons.slice(1), [...result, [dis[i], emoticons[0] * (1 - dis[i] / 100)]]);
    }
  };

  dfs(emoticons, []);

  let ans = [];

  // 가격에대해서 user적용
  for (let i = 0; i < arr.length; i++) {
    let price = 0;
    let join = 0;
    for (let j = 0; j < n; j++) {
      // 유저 하나에 대해서 가격별로 확인
      let temp = arr[i].filter((v) => v[0] >= users[j][0]);
      if (!temp.length) continue;
      let sum = 0;
      for (let k = 0; k < temp.length; k++) {
        sum += temp[k][1];
      }

      if (sum >= users[j][1]) {
        join++;
      } else {
        price += sum;
      }
    }

    if (!ans.length) ans = [join, price];

    if (ans[0] < join || (ans[0] === join && ans[1] < price)) ans = [join, price];
  }

    return ans;
}