다단계 칫솔 판매
📚 문제 설명
민호는 다단계 조직을 이용하여 칫솔을 판매하려고 한다.
이 다단계 조직에서 수익이 나면 추천인에게 자신의 수익의 10퍼센트를 주는 형식으로 진행된다고 한다.
예를 들어 아래 사진과 함계 설명하면 다음과 같다.
- young 1,200원 판매.
- edward에게 120원 배분.
- edward 120원 얻음.
- mary에게 12원 배분.
- mary 12원 얻음.
- 민호에게 1원 배분.
다단계 조직의 수익이 이처럼 분배될 때, 다단계 조직원들이 판매를 한 후 이익금의 총합은 어떻게 되는가?
👨🏻💻 풀이 과정
해당 문제를 읽고 가장 직관적으로 생각나는 풀이는 다음과 같았다.
seller순서대로 반복문 진행.- 부모를 찾아가며 돈을 건내준다.
seller반복문 종료 후 가지고 있는 금액 리턴.
그런데 이렇게 진행한 풀이에서 문제가 발생했다.
이제부터 그 문제를 보여주고 해결하는 과정을 보여주겠다.
💡1차 제출 코드 (Fail)
기본적인 로직은 위에서 말한 순서와 같다.
조금 자세히 설명하면
wallet: 각자 얻게 된 돈을 저장할 배열.SellerIndex: 현재 이익이 발생한 사람의enroll에서의 위치tax: 추천인에게 건낼 돈.parent: 추천인.
seller 배열을 하나씩 돌며 while문을 통해 위의 변수들을 갱신하며 wallet[SellerIndex] 값을 수정했다.
전체 코드
function solution(enroll, referral, seller, amount) {
// 각자 얻은 돈.
let wallet = Array.from({length: enroll.length}, _ => 0);
for (let i = 0; i < seller.length; i++) {
// 현재 이익을 본 사람의 이름.
const Name = seller[i];
// 판매금.
const Sell = amount[i] * 100;
// 현재 이익을 본 사람의 enroll 에서의 인덱스 값.
let SellerIndex = enroll.indexOf(Name);
// 추천인에게 줄 돈.
let tax = Math.floor(Sell / 10);
// 판매자가 가질 돈.
wallet[SellerIndex] += Sell - tax;
// 추천인.
let parent = referral[SellerIndex];
// 추천인을 하나씩 찾아 올라갈 반복문.
while (parent !== '-' && tax) {
// 내가 가질 금액
let tmp = tax - Math.floor(tax * 0.1);
// 내 index 값.
SellerIndex = enroll.indexOf(parent);
// 내가 가진 금액에 추가.
wallet[SellerIndex] += tmp;
// 내 추천인
parent = referral[SellerIndex];
// 내가 추천인에게 줄 돈.
tax = Math.floor(tax * 0.1);
}
}
return wallet;
}
위의 코드대로 제출을 하면 위처럼 테스트 11, 12, 13에서 시간 초과 에러가 나게 된다.
💡2차 제출 코드 (Success)
테스트 11, 12, 13을 해결하기 위해 반복문 내부를 수정하기도 하고 여러 조건문을 추가해 보았지만, 해결할 수 없었다.
그래서 어쩔 수 없이 다른분의 코드를 확인했는데 전체적인 로직은 내 로직과 동일한데,
SellerIndex를 찾는 부분에서 let SellerIndex = enroll.indexOf(Name); 가 아니라
아래와 같은 반복문을 이용하는 것을 확인했다.
for (let j = 0; j < enroll.length; j++) {
if (enroll[j] === Name) {
SellerIndex = j;
break;
}
}비록 indexOf() 함수가 O(n)이지만, 결국 원하는 값을 발견하면 return을 하기 때문에 위의 for문과 다를바 없다고 생각이 들었지만,
그래도 한번 수정해서 코드를 제출해 보았다.
2차 제출 코드
function solution(enroll, referral, seller, amount) {
// 각자 얻은 돈.
let wallet = Array.from({length: enroll.length}, _ => 0);
for (let i = 0; i < seller.length; i++) {
// 현재 이익을 본 사람의 이름.
const Name = seller[i];
// 판매금.
const Sell = amount[i] * 100;
// 현재 이익을 본 사람의 enroll 에서의 인덱스 값.
let SellerIndex = 0;
// indexOf() 대신 추가한 부분.
for (let j = 0; j < enroll.length; j++) {
if (enroll[j] === Name) {
SellerIndex = j;
break;
}
}
// 추천인에게 줄 돈.
let tax = Math.floor(Sell / 10);
// 판매자가 가질 돈.
wallet[SellerIndex] += Sell - tax;
// 추천인.
let parent = referral[SellerIndex];
// 추천인을 하나씩 찾아 올라갈 반복문.
while (parent !== '-' && tax) {
// 내가 가질 금액
let tmp = tax - Math.floor(tax * 0.1);
// 추가한 부분.
for (let j = 0; j < enroll.length; j++) {
if (enroll[j] === parent) {
SellerIndex = j;
break;
}
}
// 내가 가진 금액에 추가.
wallet[SellerIndex] += tmp;
// 내 추천인
parent = referral[SellerIndex];
// 내가 추천인에게 줄 돈.
tax = Math.floor(tax * 0.1);
}
}
return wallet;
}
솔직히 납득이 안되지만 아무튼 통과했다.
💡 3차 제출 코드 (Map 사용)
위의 통과 내역을 보면 테스트11, 12, 13 의 시간이 최대 7751이 나온 것을 알 수 있다.
따라서 다른 방법이 없나 찾게 되었고, 다른 분의 코드에서 Map을 이용하는 것을 발견했는데 너무 좋은 것 같아서
나도 내 코드의 변수를 Map으로 바꿔 보았다.
Map() 의 key와 value는 다음과 같이 설정했다.
key : 이름, value : {parent : 부모이름, budget : 숫자}
전체 코드
function solution(enroll, referral, seller, amount) {
// Map 변수 선언.
let member = new Map();
// 초기값 지정.
for (let i = 0; i < enroll.length; i++) {
member.set(enroll[i], {parent : referral[i], budget: 0})
}
// 이전 반복문과 전체적인 로직은 동일.
for (let i = 0; i < seller.length; i++) {
// 현재 확인할 사람.
let cur = member.get(seller[i]);
// 판매금.
let Money = amount[i] * 100;
while (Money && cur) {
// 추천인에게 줄 돈.
let tax = Math.floor(Money * 0.1);
// 내 이익.
cur.budget += Money - tax;
// 다음 판매금 갱신.
Money = tax;
// 다음 사람 갱신.
cur = member.get(cur.parent);
}
}
// 사람들의 이익금만 리턴하기 위해.
return enroll.map(v => member.get(v).budget);
}
이전의 풀이보다 압도적으로 빠른 속도를 볼 수 있다.
🧐 후기
indexOf() 내장 함수를 이용하는 것과 for문을 이용하는 것의 차이를 확인하기 위해 여러 글을 찾아봤는데 그 중에 한 포스트을 발견했다.
해당 포스트에서는 find(), findIndex(), indexOf() 와 for문 을 각각 비교하는 글이었다. 이 글의 내용의 결론은 for문 을 이용하는 방식이 다른 3개의 방식보다 빠르다는 것이다.
그런데 indexOf()의 로직을 검색하면 for문과 동일하게 만약 먼저 찾으면 리턴하도록 만들어졌는데 대체 무슨 차이인지 이해하기가 힘들다.
하나 확실한건 indexOf() 보다 for문이 더 성능이 좋다는 사실이다.
