[JS] 다단계 칫솔 판매

이 문제 출처가 카카오가 의심되네용

진짜 국어지문 푸는줄..

생각보다 쉬워서 다들 잘 푸셨을 것 같습니당

자 같이 한번 볼까요?

---

문제 요약

전형적인 다단계 구조네요 정말..

다단계 구조의 수익 현황을 알고 싶은 민호입니다.

이 회사는 얻은 수익의 10%를 자신을 추천해준 부모노드에게 보냅니다.

자신은 판매액의 90%를 수익으로 삼습니다.

이때 전체 수익을 return해주세요.

 

예를 들어, young이 1,200원의 수익을 올렸다고 가정합시다.

자신은 1,200원의 90%인 1,080원을 자신 몫으로 가져갑니다.

나머지 10%는 자신의 추천인인 edward에게로 갑니다.

이 10% 수익 역시 수익으로 잡히기 때문에 108원의 10%가 edward의 추천인인 mary에게 갑니다.

만약 수익이 10원 미만라면 자신이 모든 수익을 가집니다.

 

주요 제한사항

• enroll의 길이는 1 이상 10,000 이하입니다.
• referral의 길이는 enroll의 길이와 같습니다.
  • referral 내에서 i 번째에 있는 이름은 배열 enroll 내에서 i 번째에 있는 판매원을 조직에 참여시킨 사람의 이름입니다.
  • 어느 누구의 추천도 없이 조직에 참여한 사람에 대해서는 referral 배열 내에 추천인의 이름이 기입되지 않고 “-“ 가 기입됩니다. 위 예제에서는 john 과 mary 가 이러한 예에 해당합니다.
  • enroll 에 등장하는 이름은 조직에 참여한 순서에 따릅니다.
  • 즉, 어느 판매원의 이름이 enroll 의 i 번째에 등장한다면, 이 판매원을 조직에 참여시킨 사람의 이름, 즉 referral 의 i 번째 원소는 이미 배열 enroll 의 j 번째 (j < i) 에 등장했음이 보장됩니다.
• seller의 길이는 1 이상 100,000 이하입니다.
  • seller 내의 i 번째에 있는 이름은 i 번째 판매 집계 데이터가 어느 판매원에 의한 것인지를 나타냅니다.
  • seller 에는 같은 이름이 중복해서 들어있을 수 있습니다.
• amount의 길이는 seller의 길이와 같습니다.
  • amount 내의 i 번째에 있는 수는 i 번째 판매 집계 데이터의 판매량을 나타냅니다.
• 칫솔 한 개를 판매하여 얻어지는 이익은 100 원으로 정해져 있습니다.

테스트케이스

enroll	referral	seller	amount	result
["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"]	["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"]	["young", "john", "tod", "emily", "mary"]	[12, 4, 2, 5, 10]	[360, 958, 108, 0, 450, 18, 180, 1080]
["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"]	["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"]	["sam", "emily", "jaimie", "edward"]	[2, 3, 5, 4]	[0, 110, 378, 180, 270, 450, 0, 0]

 

접근 방법

우리가 흔히 다단계는 결국 회사만 돈 번다는 말을 하지 않습니까? 이 문제가 그걸 증명해주네요.

어떤 노드가 수익을 올렸다면 결국 부모노드를 타고타고 가서 회사가 어떻게든 수익을 냅니다.

 

저는 enroll과 referral의 정보로 제 입맛에 맛는 object로 데이터를 가공해보겠습니다.

1) 현재 멤버의 id.
2) 그 멤버의 추천인(parent 노드)의 id
3) 지금 노드의 이름

이렇게 가공한 다음 seller 배열을 순회하면서 거기에 맞는 object를 찾은 뒤에 amount의 90%를 수익으로 더해줍니다.이어서 그 object의 부모 id를 타고, 타고, 루트까지 타고 가면서 계속 amount의 10%의 90%?를 더해주면 해결할 수 있겠네요!

 

코드를 보면서 같이 애기하죠 생각보다 이해가 쉬우실 거에요.

 

정답 코드

function solution(enroll, referral, seller, amount) {
    const pyramid = [{ id: 0, parent: null, name: 'master' }];
    const result = Array(enroll.length).fill(0);
    
    enroll.forEach((member, i) => {
        const parentName = referral[i];
        if (parentName === "-") {
            pyramid[i + 1] = { id: i + 1, parent: 0, name: member };
        } else {
            const parentId = enroll.indexOf(parentName);
            pyramid[i + 1] = { id: i + 1, parent: parentId + 1, name: member };
        }
    });
    
    seller.forEach((member, i) => {
        const info = pyramid.find(v => v.name === member);
        const mine = amount[i] * 90;
        let tax = amount[i] * 10;
        let parentId = info.parent;
        
        result[info.id - 1] += mine;
        while (parentId > 0) {
            if (tax === 0) break;
            const nextTax = Math.floor(tax / 10);
            result[parentId - 1] += tax - nextTax;
            parentId = pyramid[parentId].parent;
            tax = nextTax;
        }
    });
    return result;
}

 

결과

약간 시간이 아쉽긴 하지만... 어거지로 통과되긴 하네요.

 

팁 1. pyramid 설명

const pyramid = [{ id: 0, parent: null, name: 'master' }];

enroll.forEach((member, i) => {
    const parentName = referral[i];
    if (parentName === "-") {
        pyramid[i + 1] = { id: i + 1, parent: 0, name: member };
    } else {
        const parentId = enroll.indexOf(parentName);
        pyramid[i + 1] = { id: i + 1, parent: parentId + 1, name: member };
    }
});

 

pyramid는 멤버의 부모노드를 담아두는 object 배열입니다.

"-"로 표기되어있는 부분은 초기화된 0번 master node를 향하게 만들었습니다.

index가 하나씩 밀리게 되니 1씩 더해주면 아래와 같이 세팅할 수 있습니다.

 

 

아래에도 표기되어있지만 이런 식으로 값을 찾을 수 있고,

모든 노드가 타고가다보면 root인 master 노드와 이어지기 때문에 -1이 나온다던가 하는 일은 없습니다.

// target => { id: 8, parent: 3, name: "young" };
const target = pyramid.find(v => v.name === "young");

 

팁 2. 90%와 10%를 반복해서 루트까지 더해줘보자!

seller.forEach((member, i) => {
    const info = pyramid.find(v => v.name === member);
    const mine = amount[i] * 90;
    let tax = amount[i] * 10;
    let parentId = info.parent;

    result[info.id - 1] += mine;
    while (parentId > 0) {
        if (tax === 0) break;
        const nextTax = Math.floor(tax / 10);
        result[parentId - 1] += tax - nextTax;
        parentId = pyramid[parentId].parent;
        tax = nextTax;
    }
});

 

내 몫인 mine을 챙기고, 상납해야하는 tax를 기준으로 반복문을 진행합니다.

while 안에서는 부모노드에 접근하기 때문에 pyramid의 0번째 index인 master노드에 접근했다면 반복문을 종료해줍시다. 제한사항에서 10원 미만인 경우도 역시 더 이상 반복할 필요가 없기 때문에 tax가 0이 된다면 종료해줍시다.

 

오늘 문제는 꽤 쉽네요!

그럼 이만!