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

programmers.co.kr/learn/courses/30/lessons/77486

코딩테스트 연습 - 다단계 칫솔 판매

---

-풀이-

처음엔 맨 말단사원부터 수수료의 10퍼를 떼고, 그 위의 상사는 모든 사원들에게 수금을 받은 뒤, 이 수금받은것과 자신이 판매한것을 합친것의 10프로를 또 상사에게 수금하는 방법으로 했더니 통과받지 못했다.

 

그래서 그림에서 나온것과 같이 판매한 물품에 대해 자신의 총금액에 90퍼를 더하고, 그걸 상사에게 10퍼를 수금하고, 이 수금받은 10퍼중 다시 90퍼는 상사의 총금액에 더하고, 나머지 10퍼를 다시 상사의 상사에게 전해주는 방식으로 풀어보았더니 통과하였다.

 

이 풀이방법으로 설명을 하면, 먼저 map을 하나 선언해준 뒤, map에 루트인 "-" 는 0번, 나머지는 순서대로 1,2,3,4,5,6 .....의 숫자를 부여해준다.

그런뒤, 부모자식관계를 referral과 enroll을 돌며 선언해준다. 0번 ("-") 의 부모는 -1로 설정해준다.

마지막으로 seller를 돌며, 위에 설명했던것처럼 자신에게 90퍼, 상사에게 10퍼를 넘기면, 상사가 수금한것의 90퍼를 더해주고, 10퍼센트를 상사의 상사에게 넘기며, 수금액이 0이되면 더이상 돌것이 없거나 부모가 -1이 된다면 ( 즉 루트노드까지 왔다면) 종료해주고 다음 seller에 대한 실행을 시켜준다.

 

-시간복잡도-

amount각각의 원소가 최대 100개이므로, 처음 시작을 100*100=10000원으로 시작해서, 0원이 되기까지 수금을 계속하는 횟수는 최대 5번이 된다. 따라서 완전이진트리의 형식으로 구조가 짜여있든, 한쪽으로 치우쳐진 트리의 구조로 짜여있든 수금은 최대 5번, 즉 상수시간 안에 해결이 가능하다. O(1).

이걸 seller의 크기만큼 반복하므로, seller의 크기를N이라 하면, O(N)이 된다.

 

-코드-

#include <string>
#include <vector>
#include<iostream>
#include<map>
using namespace std;
map<string,int> p;
int parent[100001];
int cost[100001]={0};
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    p["-"]=0;
    parent[0]=-1;
    for(int i=0;i<enroll.size();i++){
        string now=enroll[i];
        p[now]=i+1;
    }
    for(int i=0;i<referral.size();i++){
        int now=p[enroll[i]];
        int pa=p[referral[i]];
        
        parent[now]=pa;
    }
    
    for(int i=0;i<seller.size();i++){
        int now=p[seller[i]];
        int reward=amount[i]*100/10;
        
        cost[now]+=(amount[i]*100);
        
        int pa=parent[now];
        while(pa!=-1&&reward>0){
            cost[pa]+=reward;
            cost[now]-=reward;
            
            now=pa;
            pa=parent[pa];
            reward/=10;
        }
    }
   
    for(int i=0;i<enroll.size();i++){
        int now=p[enroll[i]];
        answer.push_back(cost[now]);
    }
    
    return answer;
}