다단계 칫솔 판매 [Lv. 3] (C++)

코딩테스트 연습 - 다단계 칫솔 판매 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

다단계 회사에서 직원들의 총 수익을 체크하려고합니다.

입력으로 직원 명단, 해당 직원을 초대한 명단을 받고 판매한 직원의 이름과 판매 금액을 입력받습니다.

내가 초대한 직원이 1000원을 벌면 나는 10%인 100원을 받으며, 나를 초대한 사람에게 10%인 10원을 주어야합니다.

입력들을 참고하여 모든 직원들의 수익을 출력해주세요

 

풀이 방법

해당 문제는 트리 구조의 다단계 직원 명단을 순회하기만 하면 되는 비교적 간단한 문제입니다.

하지만 데이터를 string으로 입력받기 때문에 현재 계산 중인 직원을 초대한 직원을 찾는 부분에서 

어려움을 느낄 수 있습니다. 

 

unordered_map을 이용하여 이름을 key로 index를 value로 저장하면 이는 쉽게 해결이 됩니다

(현재 index를 초대한 직원의 index를 map에서 불러올 수 있겠습니다)

 

이후 부모 노드 탐색하듯 초대한 직원을 타고 올라가며 수익을 업데이트 해주면 되겠습니다.

 

정답 코드

struct map
{
    map(int size = 1000000)
    {
        table.resize(size);
    }
    
    int GetHash(string str)
    {
        int ret = 1;
        for (int i = 0; i < str.size(); i++)
        {
            ret += str[i] * (i + 1);
            ret %= table.size();
        }
        return ret;
    }
    
    
    
    void insert(string key, int idx)
    {
        int k = GetHash(key);
        table[k].push_back({key, idx});
    }
    
    int GetValue(string key)
    {
        int k = GetHash(key);
        
        for (auto& v : table[k])
        {
            if (v.first == key)
            {
                return v.second;
            }
        }
        
        return -1;
    }
    
    vector<vector<pair<string, int>>> table;
};

자체적으로 만든 unordered_map입니다.

이름을 key로 저장 index를 value로 저장합니다.

 

map _map;
vector<int> parents(enroll.size(), -1);

for (int i = 0; i < enroll.size(); i++)
    _map.insert(enroll[i], i);

for (int i = 0; i < referral.size(); i++)
{
    if (referral[i] == "-")
        continue;

    int parent = _map.GetValue(referral[i]);
    parents[i] = parent;
}

부모 직원 index를 담을 배열을 생성했습니다

map에 직원의 이름과 index정보를 저장하였고

 

해당 map을 이용하여 나를 초대한 직원의 index를 불러와서

parents배열을 업데이트 해주었습니다.

 

vector<int> answer(enroll.size());
for (int i = 0; i < sellers.size(); i++)
{
    int seller = _map.GetValue(sellers[i]);
    int amount = amounts[i] * 100;

    while(seller >= 0)
    {
        int commission = amount;
        if (amount >= 10)
            commission = amount - (amount / 10);

        answer[seller] += commission;
        amount -= commission;
        seller = parents[seller];
    }

}

return answer;

정답을 담은 answer 배열을 만들었습니다.

판매한 직원의 index를 불러온 후 while문을 이용하여

초대한 직원들의 수익을 업데이트 해주었습니다.