[C++] Programmers Lv. 3 "다단계 칫솔 판매"

🔵 문제 링크

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

프로그래머스

 

🔵 풀이

• 조직원 구조를 트리 구조로 보고 자신의 추천인을 자신의 부모라고 가정하겠다.
• 모든 판매원은 칫솔 판매 발생 이익에서 10퍼센트를 자신의 부모에게 줘야 한다.
• 자신에게 들어온 10퍼센트 이익은 그것도 자신의 부모에게 10퍼센트를 줘야 한다.

즉 자신에게 들어온 모든 이익은 자신의 부모에게 10퍼센트를 줘야 한다.

 

따라서 문제 풀이 시 자신의 추천인(부모)만 누군지 알면 된다.

1. seller, amount의 크기만큼 돌며 칫솔 판매.
2. 판매금 계산 후 그 10퍼센트를 그 사람의 부모 -> 부모 -> 부모 -> 이어지게끔하기.

 

🔵 전체 코드

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

unordered_map<string, pair<int, string>> parent; // 자식 - <인덱스, 부모> (계층 관계)

void MLM(vector<int>& answer, string seller, int profit, int distributed, int netProfit)
{
    int idx = parent[seller].first;
    string parentName = parent[seller].second;

    // 추천자가 없다면 센터에 10퍼센트 주기
    if (seller == "-")
    {
        return;
    }

    // 이익이 10원 미만일 때
    if (profit < 10)
    {
        answer[idx] += profit;
        // cout << seller << " : " << profit << endl;
        return;
    }

    answer[idx] += netProfit;
    int nextDistributed = distributed / 10;
    MLM(answer, parentName, distributed, nextDistributed, distributed - nextDistributed);
}

// 자신의 추천인(부모)만 누군지 알면 됨
// 1. seller, amount의 크기만큼 돌며 칫솔 판매.
// 2. 판매금 계산 후 그 10퍼센트를 그 사람의 부모 -> 부모 -> 부모 -> 이어지게끔하기
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount)
{
    vector<int> answer(enroll.size());

    for (int i = 0; i < enroll.size(); i++)
    {
        parent[enroll[i]].first = i;
        parent[enroll[i]].second = referral[i];
    }

    for (int i = 0; i < seller.size(); i++)
    {
        int profit = amount[i] * 100;
        int distributed = profit / 10;
        MLM(answer, seller[i], profit, distributed, profit - distributed);
    }

    return answer;
}

 

🔵 시간 복잡도

시간 복잡도에 제일 영향을 미치는 부분을 살펴보자.

seller 별로 MLM을 실행하며, seller의 최대 사이즈를 N이라 가정한다.

MLM의 최대 실행 횟수는 트리의 깊이가 최대일 때 일어난다.

판매원의 최대 인원을 M이라 할 때, 트리의 최대 깊이는 M - 1이므로 시간 복잡도는 O(N * M)이다.