[PCCP] Lv3: 다단계 칫솔 판매(77486) 해설

문제

- 문제 링크: 다단계 칫솔 판매

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

- enroll의 길이 N, seller의 길이 M

- seller별로 enroll을 탐색하는 시간복잡도: O(N*M)

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

using namespace std;

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    
    unordered_map<string, string> parent;
    
    // parent는 판매원-판매원을 참여시킨 추천인으로 구성
    for (size_t i = 0; i < enroll.size(); ++i) {
        parent[enroll[i]] = referral[i];
    }
    
    unordered_map<string, int> total;
    
    // total은 판매원-판매원의 수익으로 구성, 수익을 0으로 초기화
    for (const auto& name : enroll) {
        total[name] = 0;
    }
    
    for (size_t i = 0; i < seller.size(); ++i) {
        int money = amount[i] * 100; // 현재 판매원 수익금
        string cur_name = seller[i]; // 실제 물건을 판 사람
        
        while (money > 0 && cur_name != "-") {
            // 실제 물건을 판 사람을 기준으로 추천인을 계속 추적하며 남은 수익의 10%를 분배
            int to_distribute = money / 10;
            total[cur_name] += money - to_distribute;
            // 현재 이름의 추천인이 있으면 현재 이름을 추천인으로 변경, 그렇지 않으면 종료
            if (parent.find(cur_name) != parent.end()) {
                cur_name = parent[cur_name];
            } else {
                break;
            }
            // 현재 판매원이 추천인으로 변경되었으므로 수익금도 맞추어 업데이트
            money = to_distribute;
        }
    }
    
    // 수익금을 answer에 업데이트해서 반환
    answer.reserve(enroll.size());
    for (const auto& name : enroll) {
        answer.push_back(total[name]);
    }
    return answer;
}

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: enroll의 길이

- M: seller의 길이

- seller별로 enroll을 탐색하므로 시간 복잡도는 O(N*M)

import java.util.HashMap;

public class Solution {

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        // parent 해시맵. key는 enroll의 노드, value는 referral의 노드로 구성됨
        HashMap<String, String> parent = new HashMap<>();
        for (int i = 0; i < enroll.length; i++) {
            parent.put(enroll[i], referral[i]);
        }

        // total 해시맵 생성
        HashMap<String, Integer> total = new HashMap<>();

        // seller 배열과 amount 배열을 이용하여 이익 분배
        for (int i = 0; i < seller.length; i++) {
            String curName = seller[i];
            // 판매자가 판매한 총 금액 계산
            int money = amount[i] * 100;
            // 판매자부터 차례대로 상위 노드로 이동하며 이익 분배
            while (money > 0 && !curName.equals("-")) {
                // 현재 판매자가 받을 금액 계산(10%를 제외한 금액)
                total.put(curName, total.getOrDefault(curName, 0) + money - (money / 10));
                curName = parent.get(curName);
                // 10% 를 제외한 금액 계산
                money /= 10;
            }
        }

        // enroll 배열의 모든 노드에 대해 해당하는 이익을 배열로 반환
        int[] answer = new int[enroll.length];
        for (int i = 0; i < enroll.length; i++) {
            answer[i] = total.getOrDefault(enroll[i], 0);
        }
        return answer;
    }

}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: enroll의 길이

- M: seller의 길이

- seller별로 enroll을 탐색하므로 O(N*M)

def solution(enroll, referral, seller, amount):
    # parent 딕셔너리 key는 enroll의 노드, value는 referral의 노드로 구성
    parent = dict(zip(enroll, referral))
    
    # total 딕셔너리 생성 및 초기화
    total = {name: 0 for name in enroll}
    
    # seller 리스트와 amount 리스트를 이용하여 이익 분배
    for i in range(len(seller)):
        # 판매자가 판매한 총 금액 계산
        money = amount[i] * 100
        cur_name = seller[i]
        # 판매자로부터 차례대로 상위 노드로 이동하며 이익 분배
        while money > 0 and cur_name != "-":
            # 현재 판매자가 받을 금액 계산(10%를 제외한 금액)
            total[cur_name] += money - money // 10
            cur_name = parent[cur_name]
            # 10%를 제외한 금액 계산
            money //= 10
    # enroll 리스트의 모든 노드에 대해 해당하는 이익을 리스트로 반환
    return [total[name] for name in enroll]

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: enroll의 길이

- M: seller의 길이

- seller와 enroll의 길이가 같고 각각 한 번씩 순회: O(N)

function solution(enroll, referral, seller, amount) {
    // parent 오브젝트 key는 enroll의 노드, value의 referral의 노드로 구성
    let parent = {};
    
    for(let i = 0; i < enroll.length; i++) {
        parent[enroll[i]] = referral[i];
    }

    
    // total 오브젝트 생성 및 초기화
    let total = {};
    for(let name of enroll) {
        total[name] = 0;
    }
    
    // seller 배열과 amount 배열을 이용하여 이익 분배
    for(let i = 0; i < seller.length; i++) {
        // 판매자가 판매한 총 금액 계산
        let money = amount[i] * 100;
        let curName = seller[i];
        
        // 판매자부터 차례대로 상위 노드로 이동하여 이익 분배
        while(money > 0 && curName != "-") {
            // 현재 판매자가 받을 금액 계산(10%를 제외한 금액)
            total[curName] += money - Math.floor(money / 10);
            curName = parent[curName];
            
            // 10%를 제외한 금액 계산
            money = Math.floor(money / 10);
        }
    }
    
    // enroll 배열의 모든 노드에 해당하는 이익을 배열로 반환
    return enroll.map(name => total[name]);
}

solution 2)

import

solution 3)

import