[프로그래머스][C++] 다단계 칫솔 판매 (250)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

프로그래머스

 

생각의 흐름

우선 2가지 코드를 설명할건데, 처음 풀이는 내가 잘못 풀었던 방식이다.

 

1) 잘못 푼 방식 (테스트 3, 6 번만 통과)

처음 생각한 방식은 center(ROOT)를 기준으로 DFS를 진행하면 되겠다고 생각하였다.

 

1. 각 노드마다 자식노드를 저장해둔다.

2. center부터 시작해서 자식으로 이동한다.

    2-1. 자식이 없다면 자신의 수입을 계산하고, 10%를 반환한다.

    2-2. 자식이 있다면 해당 자식 함수를 호출한다.

3. root까지 계산이 완료된다면 종료

 

이를 코드로 나타내면 다음과 같다.

#include <bits/stdc++.h>

using namespace std;

unordered_map<string, vector<string>> MAP;
unordered_map<string, int> PROFIT;
unordered_map<string, int> RES;


int go(string name) {
    if(MAP[name].empty()) {
        int income = PROFIT[name];
        int send_money = (income * 0.1);
        if(send_money < 1) {
            return 0;
        }
        int my_money = income - send_money;
        RES[name] += my_money;
        return send_money;
    }

    int send = 0;
    for(auto next : MAP[name]) {
        int from_child_income = go(next);
        int send_money = (from_child_income * 0.1);

        if(send_money < 1) {
            send_money = 0;
        }
        int my_money = from_child_income - send_money;

        send += send_money;
        RES[name] += my_money;
    }

    if(PROFIT[name] != 0) {
        int now_income = PROFIT[name];
        int now_send_money = (now_income * 0.1);
        if(now_send_money < 1) {
            now_send_money = 0;
        }
        RES[name] += now_income - now_send_money;
        send += now_send_money;
    }

    return send;
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;

    int len = enroll.size();
    for(int i = 0; i < len; i++) {
        if(referral[i] != "-") {
            MAP[referral[i]].push_back(enroll[i]);
        } else {
            MAP["center"].push_back(enroll[i]);
        }
    }

    len = seller.size();
    for(int i = 0; i < len; i++) {
        PROFIT[seller[i]] = amount[i] * 100;
    }

    go("center");

    for(auto name : enroll) {
        answer.push_back(RES[name]);
    }

    return answer;
}

위 코드는 기본 테스트 케이스 2개는 통과하지만, 제출시 3, 6번을 제외하고는 실패한다.

 

무엇이 문제였을까? 다음 그림을 살펴보자.

모든 Child가 자기 자신의 수입에서 10%인 5원을 반환한다고 해보자.

각각이 5씩 반환한다면 Parent는 5원의 10%는 0.5원으로, 1원 미만이기 때문에 자신이 5원을 전부 갖게된다.

따라서 Parent의 부모에게는 0원이 전달된다.

 

하지만 위에서 내가 구현한 코드는 다음과 같이 동작한다.

모든 자식의 금액을 다 합친후에, 여기서 10% 제공하니 2원을 반환하게 된다.

int send = 0;
for(auto next : MAP[name]) {
    int from_child_income = go(next);
    int send_money = (from_child_income * 0.1);

    if(send_money < 1) {
        send_money = 0;
    }
    int my_money = from_child_income - send_money;

    send += send_money;
    RES[name] += my_money;
}

자식을 전부 순회하면서 자식으로 부터 받은 금액을 전부 합쳐주고 있다.

 

2) 다시 푼 방식

이번에는 root부터가 아니라, 모든 자식으로 부터 역으로 root로 올라갈것 이다.

모든 자식이 DFS를 통해서 root에 도달할때 까지 자신의 10%를 반환해주면 된다.

 

각 자식별로 진행되기 때문에 이전과 같은 문제는 발생하지 않는다.

코드로 살펴보면 이해될 것 이다!

 

나의 코드

#include <bits/stdc++.h>

using namespace std;

unordered_map<string, string> PARENT;
unordered_map<string, int> PROFIT;

void go(string name, int from_child) {
    if(name == "center") return;

    int to_parent_income = from_child / 10;
    PROFIT[name] += (from_child - to_parent_income);

    if(to_parent_income < 1) {
        return;
    }

    go(PARENT[name], to_parent_income);
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;

    int len = enroll.size();
    for(int i = 0; i < len; i++) {
        if(referral[i] != "-") {
            PARENT[enroll[i]] = referral[i];
        } else {
            PARENT[enroll[i]] = "center";
        }
    }

    len = seller.size();
    for(int i = 0; i < len; i++) {
        go(seller[i], amount[i] * 100);
    }

    for(auto name : enroll) {
        answer.push_back(PROFIT[name]);
    }

    return answer;
}