[프로그래머스] 다단계칫솔 판매

문제 요약

• 트리구조가 부모 - 자식 관계로써 주어집니다.
• 부모는 자식이 발생시킨 수익의 10퍼를 갖습니다.
• 자식이 발생시킨 수익 역시 나의 수익이므로, 나의 부모에게 10퍼가 전달이 되어야합니다.
• 떼어줄 10프로를 계산할 때 소수자리는 버림합니다.

아이디어

트리의 부모들만 저장해놓고, 수익이 발생할 때마다 조상들을 돌며 10퍼센트씩 떼어주는 작업을 한다.

떼어주는 값을 int 형으로 저장하여 부모에게 덧셈, 나에게선 뺄셈을 한다.

틀린 풀이(dfs 후위 순회)

자식들로부터 발생한 수익들+순수 내 수익을 부모한테 10퍼를 떼줘야한다는 점이 헷갈렸다.

나의 경우 dfs 후위순회를 하며 내가 최종적으로 갖게 되는 돈을 계산한 뒤(자식들로부터 발생한 수익들+순수 내 수익) 커어어어다란 덩어리에서 내 엄마한테 10퍼를 떼주었다.

그런데 문제에서 의도한 바는 각 수익이 발생할 때마다 10퍼센트씩 올라가면서 배분이 되는 구조이다. 나눗셈이 더 작은 숫자에서 발생하므로 엄마한테 상납하는 금액이 위의 풀이보다 적다.

극단적인 예
나 : 자식1 9원 상납+자식2 9 원 상납 +나 100원 벌음
틀린 풀이 : 내가 118원 벌었으니 11원을 엄마한테 상납
문제가 의도한 풀이 :
자식1이 상납한 9원/10 = 0 원을 엄마한테 상납
자식2이 상납한 9원/10 = 0 원을 엄마한테 상납
내가 번 100원/10 = 10원을 엄마한테 상납
=> 총 10원을 엄마한테 상납

틀린코드

#include <string>
#include <vector>
#include<map>
#include<vector>
#include<iostream>
using namespace std;
//후위 순회해야함 dfs
map<string,vector<string>> tree;//tree
map<string,int> money;

int dfs(string cur){
    vector<string> children = tree.find(cur)->second;
    for(int i = 0;i<children.size();i++){
        int sugeum = dfs(children[i])/10;
        money.find(cur)->second += sugeum;
        money.find(children[i])->second-=sugeum;
    }
    return money.find(cur)->second;
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    tree.insert({"-",vector<string>()});
    money.insert({"-",0});
    for(int i = 0;i<enroll.size();i++){
        string child = enroll[i], mother = referral[i];
        
        tree.insert({child, vector<string>()});
        money.insert({child, 0});//child는 한번씩만 나옴.
        tree.find(mother)->second.push_back(child);
    }
    
    for(int i = 0;i<seller.size();i++){
        money.find(seller[i])->second+=amount[i]*100;
    }
    dfs("-");
    
    for(int i = 0;i<enroll.size();i++){
        answer.push_back(money.find(enroll[i])->second);
    }
    
    return answer;
}

삽질

배열 크기 문제

처음에 부모가 민호(center "-") 인 아이들 예) 존, 마리
에 대해 부모를 -1로 마킹 했다.(이유는 그닥 크지 않고 그냥 rev_idx가 enroll이랑 일치하게 하기 위해서였다.)
그렇게 했을 때 while문에서 -1이 나오면 부모에게 분배하는 작업을 멈추는데 여기서 부모(center)의 수익은 아무래도 상관 없지만 나의 수익이 줄어들지 않는다.

그래서 민호를 0번으로 뒀는데 배열사이즈는 그대로 enroll size여서 segmentation fault가 났었다.

mother me 세대교체

mother<-할머니
me <- mother
이렇게 했을 때 mother와 me가 같아지는...실수를 하였다
statement의 순서를 바꿔주기만해도 생기지 않는 문제인데
이거 디버깅 한다고 시간을 많이 썼다..

잘한점

수금액을 int형에 저장

소숫점 관련해서 혹시라도 형변환이 잘못이루어지는 것을 방지하는 효과가 있다.(사실 cpp라 연산하면 int 형으로 변환되지만... 그냥 심리적 안정감...)

reverse index(string -> int idx)

정답코드

#include <string>
#include <vector>
#include<unordered_map>
#include<iostream>
using namespace std;
unordered_map<string,int> rev_idx;
//오히려 부모 번호만 알고 있는게 더 도움됨
//굳이 따지자면 union find인듯
int tab[10001];
int money[10001];

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    rev_idx.insert({"-",0});
    tab[0] = -1;
    for(int i = 0;i<enroll.size();i++){
        string child = enroll[i], mother = referral[i];
        rev_idx.insert({child,i+1});
        int mother_n = rev_idx.find(mother)->second;
        tab[i+1] = mother_n;
    }
    for(int ctr= 0;ctr<seller.size();ctr++){
        int me = rev_idx.find(seller[ctr])->second;
        money[me] += amount[ctr]*100;
        int sugum = (amount[ctr]*100)/10;
        int mother = tab[me];
        while(sugum>0 &&mother!=-1){
            money[mother]+=sugum;
            money[me] -=sugum;
            //세대교체
            me = mother;
            mother = tab[mother];
            sugum = sugum/10;
        }
    }
    for(int i = 1;i<=enroll.size();i++){
        answer.push_back(money[i]);
    }
    return answer;
}