[DFS] 이모티콘 할인행사

[ericagong]

⭐ 성찰

1. 계산공식 확실히 세우고 문제풀기. 식 세워두지 않으면, 코딩 과정에서 안일하게 실수 발생! ㄴ 할인율에 따른 금액 계산 : 가격 * (100-할인율) / 100
2. for문 처리 시, 마지막 요소까지 처리되지 않을 수 있으니, 판단 조건문은 모든 계산 처리 이후에 작성하기 -> 오류 발생

   for (let i = 0; i < emoticons.length; i++) {
   if (user_rev >= price) {
   // 비교판단 식 사전에 두었을 때, 마지막 요소가 미처리 됨 -> 🐛 오류 발생 지점 🐛 
   user_rev = 0;
   plus_mem += 1;
   break;
   }
   if (discounts[i] >= rate) {
   // 할인율 식 세울 때 주의: 가격 * (100-할인율) / 100
   const emoji_price = emoticons[i] * ((100 - discounts[i]) / 100); -> 🐛 오류 발생 지점 🐛 
   user_rev += emoji_price;
   }
   }

❓ 문제 상황

프로그래머스 LV2. 이모티콘 할인행사

👨‍💻 문제 해결

✅ 1차 풀이: DFS -> 순열 -> 완전탐색

1. DFS로 모든 이모티콘에 적용될 수 있는 할인율 순열 생성
2. DFS 종료 시, 각 할인율 순열에 대해 [이모티콘 플러스 전환 사용자 수, 이모티콘 매출액] 계산하여 results에 추가
3. results를 (1) 이모티콘 플러스 전환 사용자 수 내림차순 (2) 이모티콘 매출액 내림차순으로 정렬한 뒤, 첫번째 요소 반환

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

function calc(users, emoticons, discounts) { let plus_mem = 0; let acc_rev = 0; users.forEach(([rate, price]) => { let user_rev = 0; for (let i = 0; i < emoticons.length; i++) { if (discounts[i] >= rate) { // 할인율 식 세울 때 주의: 가격 (100-할인율) / 100 const emoji_price = emoticons[i] ((100 - discounts[i]) / 100); user_rev += emoji_price; } if (user_rev >= price) { // 비교 식 사전인지 사후인지 잘 파악 user_rev = 0; plus_mem += 1; break; } } acc_rev += user_rev; });

return [plus_mem, acc_rev]; }

const rates = [10, 20, 30, 40]; const discounts = []; let results = []; function dfs(cnt, users, emoticons) { if (cnt === emoticons.length) { const [plus_mem, acc_rev] = calc(users, emoticons, discounts); results.push([plus_mem, acc_rev]); return; }

for (let i = 0; i < rates.length; i++) { discounts.push(rates[i]); dfs(cnt + 1, users, emoticons); discounts.pop(); } }

function solution(users, emoticons) { dfs(0, users, emoticons); results.sort((a, b) => { if (a[0] !== b[0]) return b[0] - a[0]; // 이모티콘 플러스 가입자 내림차순 return b[1] - a[1]; // 이모티콘 매출 내림차순 }); return results[0]; }