[프로그래머스] 이모티콘 할인행사 / JavaScript / Level 2

🚩문제 주소

📄 풀이

완전탐색

시간복잡도는 O(n * m * 4**n)이므로 완전 탐색으로 충분히 풀 수 있었습니다.

1. 가장 먼저 중복 순열을 이용하여 할인율들의 모든 경우의 수를 담은 배열을 만들어 줍니다.
2. 중복 순열의 각 할인율 배열 별로 아래의 과정을 반복합니다.

• 이모티콘 플러스 서비스 가입자 변수와 각 사용자 별 이모티콘에 사용한 비용 배열을 선언한 뒤 값을 할당합니다.
• 각 할인율 별로 유저의 최소 구매 할인율이 이모티콘 할인율 이하이면 costs배열에 비용을 계산해서 인덱스 별로 저장합니다.
• costs배열에서 각 원소가
  - 최대 비용을 넘으면 이모티콘 구매 비용에 더합니다.
  - 넘지 않는다면 이모티콘 플러스 서비스 가입자를 증가시킵니다.
• 정답배열에 [서비스 가입자, 사용한 비용] 형식으로 넣습니다.

3. 정답배열을 이모티콘 플러스 서비스 가입자 순으로 내림차순 정렬합니다.
   가입자가 같은 배열이 있다면 사용한 비용 순으로 다시 내림차순 정렬합니다.
   가장 앞에 있는 배열이 최대값이므로 0번 배열을 반환합니다.

👨‍💻 코드

function Permutation(arr, selectNum) {
  // 중복 순열 구하기
  const result = [];

  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixed = v;
    const restArr = arr;
    const permutationArr = Permutation(restArr, selectNum - 1);
    const combineFix = permutationArr.map((v) => [fixed, ...v]);
    result.push(...combineFix);
  });

  return result;
}

function solution(users, emoticons) {
  // 시간 복잡도: O(m * n * 4**n)
  const answer = [];
  const permutation = Permutation([10, 20, 30, 40], emoticons.length);
  // 할인율의 중복 순열 구하기

  permutation.forEach((combi) => {
    let service = 0; // 이모티콘 플러스 서비스 가입자
    const costs = Array(users.length).fill(0); 
    // 각 사용자 별 이모티콘에 사용한 비용

    combi.forEach((c, ci) => {
      // 각 할인율 별로
      users.forEach((user, ui) => {
        // 유저의 최소 구매 할인율이 이모티콘 할인율 이하이면 
        // costs배열에 비용을 계산해서 저장
        if (user[0] <= c) 
          costs[ui] += emoticons[ci] * ((100 - c) / 100);
      });
    });

    // costs배열에서 각 원소가 유저의 최대 비용을 넘으면 이모티콘 구매 비용에 더하기
    // 넘지 않으면 이모티콘 플러스 서비스 가입자 증가
    let sum = 0;
    for (let i = 0; i < costs.length; i++) {
      if (costs[i] < users[i][1]) {
        sum += costs[i];
      } else {
        service++;
      }
    }
    answer.push([service, sum]); // 정답배열에 추가
  });

  // 이모티콘 플러스 서비스 가입자 순으로 내림차순
  // 가입자가 같을 경우 이모티콘에 사용한 비용 순으로 내림차순
  // 가장 맨 앞에 있는게 최대값
  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];
}