선밥의 공부하는 블로그

다단계 칫솔 판매

문제 링크

다단계 칫솔 판매

분석

각 판매원이 얻은 최종 수익을 enroll의 값 순서대로 배열에 담아 반환해야합니다.

각 판매원은 한 명의 추천인을 가질 수 있습니다.
만약, 추천인이 없는 경우 "-"로 표시됩니다.

판매원은 칫솔 한 개당 100원의 수익을 얻습니다.
판매 수익의 10%는 추천인에게 전달되며, 나머지 90%는 판매원이 가져갑니다.
추천인에게 전달된 10% 수익도 동일한 방식으로 상위 추천인에게 분배됩니다.
분배 금액이 1원 미만이 되면 더 이상 분배하지 않습니다.

각 판매자가 얻은 수익을 추천인에게 전달하는 방식으로 진행됩니다.
즉, 이 문제는 자식이 부모를 확인하고 올라가는 방식으로, 부모-자식 관계를 관리하는 알고리즘입니다.

  • enroll: 판매원들의 이름 목록입니다.
  • referral: 각 판매원의 추천인 목록입니다.
  • seller: 판매를 진행한 판매원들의 이름 목록입니다.
  • amount: 각 판매원이 판매한 칫솔 개수입니다.

풀이

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

using namespace std;

// 수익을 상위 추천인에게 분배하는 재귀 함수
void distributeProfit(int sellerIndex, int profit, const vector<int>& referral, vector<int>& answer)
{
    // 수익이 1원 미만이거나 추천인이 없을 경우 종료
    if (profit < 1 || sellerIndex == -1)
    {
        return;
    }
    
    // 전체 수익의 10%를 추천인에게 전달할 커미션으로 설정
    int commission = profit / 10;
    // 현재 판매자는 전체 수익 중 90%를 가져갑니다.
    answer[sellerIndex] += profit - commission;
    // 추천인에게 커미션을 전달합니다.
    distributeProfit(referral[sellerIndex], commission, referral, answer);
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    
    // 이름으로 인덱스를 저장합니다.
    unordered_map<string, int> nameToIndex;
    
    // 총 참여자 수
    int n = enroll.size();
    
    // 각 참여자의 이름을 인덱스로 저장합니다.
    for (int i = 0; i < n; ++i)
    {
        nameToIndex[enroll[i]] = i;
    }
    
    // 각 참여자의 추천인 인덱스를 저장합니다.
    // 만약 추천인이 없는 경우 -1을 저장하고, 있는 경우 해당하는 인덱스를 저장합니다.
    vector<int> referralIndex(n);
    for (int i = 0; i < n; ++i)
    {
        referralIndex[i] = (referral[i] == "-") ? -1 : nameToIndex[referral[i]];
    }
    
    // 수익 배열을 초기화하고, 판매 기록에 따라 수익을 계산하고 분배합니다.
    answer.resize(n, 0);
    for (int i = 0; i < seller.size(); ++i)
    {
        // 판매자 이름으로 인덱스를 가져옵니다.
        int sellerIndex = nameToIndex[seller[i]];
        // 수익을 구하고, 분배합니다.
        int profit = amount[i] * 100;
        distributeProfit(sellerIndex, profit, referralIndex, answer);
    }
    
    return answer;
}

unordered_map을 사용해서 판매원의 이름을 인덱스로 저장합니다.
vector<int>를 사용하여 각 판매원의 추천인 인덱스를 저장합니다.
각 판매원의 수익은 answer에 저장합니다.

판매원과 추천인의 관계를 인덱스로 저장하여 저장하고, 각 판매원의 판매 수익을 계산합니다.
계산된 수익에서 distributeProfit함수를 사용해 수익을 분배하게 됩니다.

distributeProfit함수는 수익 분배를 재귀적으로 구현하여 추천인에게 수익을 전달합니다.
이 함수의 종료 조건은 분배 금액이 1원 미만이 되거나 추천인이 없는 경우 분배를 종료합니다.

성능 요약

시간 복잡도는 $O(n + m \times log \ p)$입니다.

  • 각 참여자의 이름을 인덱스로 저장하는 반복문 $O(n)$
  • 각 참여자의 추천인 인덱스를 저장하는 반복문 $O(n)$
  • 판매 수익을 분배하는 반복문 $O(m \times log \ p)$
    • m은 판매자의 수를 의미합니다.
    • p는 최대 수익을 의미합니다.

공간 복잡도는 $O(n)$입니다.

  • 이름으로 인덱스를 저장하는 unordered_map<string, int> nameToIndex $O(n)$
  • 참여자의 추천인 인덱스를 저장하는 vector<int> referralIndex $O(n)$
  • 각 판매원의 최종 수익을 저장하는 vector<int> answer $O(n)$
  • 재귀 호출 스택 깊이 $O(log_{10} \ p) \approx 6$
  • $O(n) + O(n) + O(n)$
테스트 성능

테스트 1 〉 통과 (0.02ms, 4.2MB)
테스트 2 〉 통과 (0.02ms, 4.2MB)
테스트 3 〉 통과 (0.05ms, 3.66MB)
테스트 4 〉 통과 (0.06ms, 4.18MB)
테스트 5 〉 통과 (0.11ms, 4.18MB)
테스트 6 〉 통과 (4.31ms, 6.7MB)
테스트 7 〉 통과 (7.05ms, 6.75MB)
테스트 8 〉 통과 (4.90ms, 6.52MB)
테스트 9 〉 통과 (4.97ms, 7.58MB)
테스트 10 〉 통과 (12.08ms, 18.6MB)
테스트 11 〉 통과 (14.31ms, 18.7MB)
테스트 12 〉 통과 (9.55ms, 18.7MB)
테스트 13 〉 통과 (9.40ms, 18.7MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글