알고리즘 문제 풀이(프로그래머스 - 이모티콘 할인행사)

프로그래머스 LEVEL 2(이모티콘 할인행사)

• 사용 언어 : javascript

• 해결 날짜 : 2023-05-14

• 해결 방법 :

  • users의 길이가 최대 100, emoticons의 길이가 최대 7이기 때문에 할인의 모든 경우의 수를 구해서 문제를 해결
    • O(m ^ m _ n), 최대 경우 7^7 _ 100
  • 재귀를 통해 10, 20, 30, 40으로 만들 수 있는 모든 할인 경우의 수(dicountCases) 계산
    • dicountCases를 돌며
      • 사용자마다 할인율 별 이모티콘을 전부 구매했을 때 자신의 최대 구매 비용 이상이 된다면 플러스 이용자 수(temp[0]) 증가
      • 그 외의 경우 판매액(temp[1]) 증가
    • 구해진 모든 경우의 수를 플러스 이용자 수 내림차순, 판매액 내림차순 정렬
    • 첫번째 값(최대) 반환

• 회고 :

  • x

• 코드

  function solution(users, emoticons) {
    const getDiscountCases = () => {
      const discountRates = [10, 20, 30, 40];
      const cases = [];
  
      const _getDisCountCases = (c) => {
        if (c.length === emoticons.length) {
          cases.push(c);
          return;
        }
  
        for (let i = 0; i < discountRates.length; i++) {
          _getDisCountCases([...c, discountRates[i]]);
        }
      };
  
      _getDisCountCases([]);
  
      return cases;
    };
  
    const dicountCases = getDiscountCases();
  
    const candidates = dicountCases
      .map((discountCase) => {
        const temp = [0, 0];
  
        users.forEach(([discountRate, limit]) => {
          let count = 0;
  
          for (let i = 0; i < discountCase.length; i++) {
            if (discountRate <= discountCase[i]) {
              count += (emoticons[i] * (100 - discountCase[i])) / 100;
            }
          }
  
          if (count >= limit) {
            temp[0] += 1;
          } else {
            temp[1] += count;
          }
        });
  
        return temp;
      })
      .sort((a, b) => {
        if (a[0] === b[0]) {
          return b[1] - a[1];
        } else {
          return b[0] - a[0];
        }
      });
  
    return candidates[0];
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges