[Programmers] 이모티콘 할인행사 - Javascript

INDEX

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

프로그래머스

 

Solution

카카오에서 내는 코딩테스트 문제는 문제가 길어 이해하는데도 오래 걸립니다.

 

이모티콘 할인율은 10%, 20%, 30%, 40% 중 하나입니다. 만약 이모티콘이 2개라면 나올 수 있는 할인율을 배열로 나타낸다면 [10%, 10%], [10%, 20%], [10%, 30%], [10%, 40%], [20%, 10%], [20%, 20%]... 이렇게 총 16가지가 됩니다. 즉, 순서 상관없이 뽑는 조합의 수는 4의 N(이모티콘 개수) 제곱이 됩니다.

 

이렇게 해서 이모티콘의 할인율 배열을 얻었다면 이제 각 사용자를 순회하면서 이 사용자가 이모티콘을 살 사람인지 혹은 플러스 가입자가 될 사람인지 검사를 하고 플러스 가입자 수가 최대가 되도록, 가입자 수가 같다면 매출이 최대가 되도록 하는 할인율을 선택하면 됩니다.

 

우선 모든 사용자의 이모티콘 구매 비용을 구하는 함수를 구현합니다. 단순히 배열의 합을 구하는 함수입니다.

function getSumOfArray(arr) {
  let sum = 0;
  arr.forEach((item) => {
    sum += item;
  });
  return sum;
}

solution 함수의 내부는 아래와 같습니다.

function solution(users, emoticons) {
  let answer = [];
  function dfs(idx=0, percentArr=[]) {
    if (idx === emoticons.length) {
      //사용자를 순회하면서 살 사람인지, 플러스 가입자가 될 사람인지 검사합니다.
      let members = 0;
      let amounts = new Array(users.length).fill(0);
      for (let i = 0; i < users.length; i++) {
        const user = users[i];
        for (let j = 0; j < percentArr.length; j++) {
          const percent = percentArr[j];
          const emoticon = emoticons[j];
          if (percentArr[j] >= user[0]) { //사용자의 비율보다 할인율이 크다면 구매합니다.
            amounts[i] += emoticon - (percent / 100) * emoticon;
          }
        }
        
        if (amounts[i] >= user[1]) { //사용자의 금액보다 구매비용이 크다면 플러스 가입자가 됩니다.
          amounts[i] = 0; //플러스 가입자가 되니 구매비용은 0으로 초기화합니다.
          members += 1;
        }
      }
      return answer.push([members, getSumOfArray(amounts)]);
  	}

    for (let i = 1; i <= 4; i++) {
      const percent = i * 10; //할인율은 10%, 20%, 30%, 40% 중 하나를 선택합니다.
      percentArr.push(percent);
      dfs(idx + 1, percentArr);
      percentArr.pop();
    }
  }
  dfs();
}

이렇게 되면 answer 배열 안에는 다음과 같은 원소들이 쌓입니다.

원소의 첫 번째 원소는 멤버십에 가입한 사용자의 수, 두 번째 원소는 총매출비용입니다.

이 배열을 첫 원소 내림차순, 두 번째 원소 내림차순으로 정렬을 한 후에 첫 번째 원소가 정답이 됩니다.

return answer.sort((a, b) => {
    if (a[0] > b[0]) return b[0] - a[0];
    else if (a[0] === b[0]) return b[1] - a[1];
  })[0];

 

전체 코드

function solution(users, emoticons) {
  let answer = [];
  function dfs(idx = 0, percentArr = []) {
    if (idx === emoticons.length) {
      let members = 0;
      let amounts = new Array(users.length).fill(0);
      for (let i = 0; i < users.length; i++) {
        const user = users[i];
        for (let j = 0; j < percentArr.length; j++) {
          const percent = percentArr[j];
          const emoticon = emoticons[j];
          if (percentArr[j] >= user[0]) {
            amounts[i] += emoticon - (percent / 100) * emoticon;
          }
        }
        if (amounts[i] >= user[1]) {
          amounts[i] = 0;
          members += 1;
        }
      }

      return answer.push([members, getSumOfArray(amounts)]);
    }

    for (let i = 1; i <= 4; i++) {
      const percent = i * 10;
      percentArr.push(percent);
      dfs(idx + 1, percentArr);
      percentArr.pop();
    }
  }
  dfs();
  return answer.sort((a, b) => {
    if (a[0] > b[0]) return b[0] - a[0];
    else if (a[0] === b[0]) return b[1] - a[1];
  })[0];
}
function getSumOfArray(arr) {
  let sum = 0;
  arr.forEach((item) => {
    sum += item;
  });
  return sum;
}