Programmers - 다단계 칫솔 판매

---

title: Programmers - 다단계 칫솔 판매
date: 2022-08-23
tags:

• Algorithm

---

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

문제 요약

트리 구조의 다단계 조직이 주어진다.
어떠한 인원이 물건을 판매하면 판매 수익의 10%를 부모에게 배분하며, 부모는 받은 수익의 10%를 다시 부모에게 배분하는 작업이 이루어진다.
10%가 소수일 경우 원 단위로 내림을 한다.
각 인원이 최종적으로 분배받는 수익을 vector에 넣어 return한다.

문제 풀이

적절한 Tree를 만들어 재귀적으로 반복하면 된다.
처음에는 모든 수익을 이용하여 이를 반복하였으나, 이 경우 수익 처리에 문제가 생긴다.
5원씩 10번을 벌었다면 부모에게 분배되는 수익이 내림으로 인하여 0원이 되지만, 이를 50원으로 취급할 경우 부모가 5원을 가져가는 불상사가 생긴다.
이로 인하여 수익이 발생될 때마다 분배 작업을 해주면 된다.


각 노드의 수익, 부모의 index를 묶어 저장한다.
모든 노드의 정보를 구축한 후, 수익이 생길 때마다 distributeIncome 함수를 재귀적으로 호출하며 수익을 갱신한다.

프로그램

#include <string>
#include <vector>
#include <unordered_map>

using std :: vector ;
using std :: string ;
using std :: unordered_map ;

struct nodeInfo
{
    int iIncome ;
    int iParentIndex ;
} ;

void distributeIncome ( vector < nodeInfo > & vNode , int iIndex , int iAmount )
{
    if ( -1 == iIndex )
        return ;

    int iDistributeIncome = iAmount * 0.1 ;
    vNode [ iIndex ].iIncome += iAmount - iDistributeIncome ;

    if ( 0 < iDistributeIncome )
        distributeIncome ( vNode , vNode [ iIndex ].iParentIndex , iDistributeIncome ) ;
}

vector < int > solution ( vector < string > enroll , vector < string > referral , vector < string > seller , vector < int > amount )
{
    int iUserSize = enroll.size () ;
    int iSellerSize = seller.size () ;
    vector < int > answer ;
    vector < nodeInfo > vNode ;
    unordered_map < string , int > umUserIndex ;        // < user name , user index >



    umUserIndex [ "-" ] = -1 ;
    for ( int i = 0 ; i < iUserSize ; ++i )
    {
        umUserIndex [ enroll [ i ] ] = i ;
        int iParentIndex = umUserIndex [ referral [ i ] ] ;

        vNode.push_back ( { 0 , iParentIndex } ) ;
    }

    for ( int i = 0 ; i < iSellerSize ; ++i )
    {
        int iIndex = umUserIndex [ seller [ i ] ] ;
        vNode [ iIndex ].iIncome += amount [ i ] * 90 ;
        distributeIncome ( vNode , vNode [ iIndex ].iParentIndex , amount [ i ] * 10 ) ;
    }

    for ( int i = 0 ; i < iUserSize ; ++i )
    {
        answer.emplace_back ( vNode [ i ].iIncome ) ;
    }


    return answer ;
}