프로그래머스 - 다단계 칫솔 판매

문제

오늘의 챌린지 문제이다. 문제를 처음 봤을 때 지문이 되게 길어서 솔직히 풀기 싫었지만 요즘 코테에서 긴 문제가 많이 나오기 때문에 풀어봤다

문제는 간단히 정리하면 다단계라는 의미에서 계층적 구조가 형성된다. A가 B를 끌어들이고 B가 C를 끌어들이고 D를 끌어들이고...

그래서 추천인 제도같이 C가 어떤 수익을 벌면 90%만 먹고 10%는 B에게 간다. B가 먹은 10%에서 또 90%만큼 먹고 남은 10%가 A에게 간다. A도 남은 10%는 센터에게 돌려준다

그래서 판매 목록을 가지고 계산해 마지막으로 어떤 사람이 얼마의 수익을 냈는지를 물어보는 문제이다. 참고로 센터는 계산에서 제외한다

풀이

계층적이라는 의미가 들어간 문제라 트리를 생각했다

하지만 트리를 직접 구현할 필요가 없고 A의 부모가 누군지, B의 부모가 누군지를 기록하면 된다(부모라는건 추천인을 뜻함)

그래서 처음에 enroll과 referral을 가지고 부모 배열(parent)을 완성한다. 먼저 이름이니까 문자열이라 배열로 다루기 까다롭다. 그래서 이름 중복도 없으니 이름을 그냥 숫자로 바꿔버리자

map<string, int>에 순서대로 담고 referral을 돌면서 만약 추천인이 없으면(센터) 부모를 -1로 설정하고 추천인이 있으면 부모로 설정한다

그 다음 핵심 로직인 판매 목록을 루프로 돌면서 가장 먼저 판매원이 누군지를 파악 후 이익을 계산하고 profit이라는 배열에 90%의 수익을 더해준다

그 다음 parent 배열을 이용해 부모가 -1이 될 때까지(추천인이 없을 때까지) while문을 돌면서 돈을 계산해가며 수익에 더해준다. 이때 문제에서 요구하는 값에 따라 올림으로 계산함

계산이 전부 끝나면 answer에 각각의 수익을 넣어서 리턴하면 끝

코드

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

int parent[10004];
int profit[10004];
map<string, int> info;

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    
    for(int i = 0; i < enroll.size(); i++)
    {
        info[enroll[i]] = i;
    }
    
    for(int i = 0; i < referral.size(); i++)
    {
        if(referral[i] == "-")
        {
            parent[i] = -1;
        }
        else
        {
            parent[i] = info[referral[i]];
        }
    }
    
    for(int i = 0; i < seller.size(); i++)
    {
        int sellerNum = info[seller[i]];
        int price = amount[i] * 100;
        profit[sellerNum] += price * 0.9;
        
        while(parent[sellerNum] != -1)
        {
            sellerNum = parent[sellerNum];
            price = price * 0.1;
            profit[sellerNum] += ceil(price * 0.9);
        }
    }
    
    for(int i = 0; i < enroll.size(); i++)
    {
        answer.push_back(profit[i]);
    }
    
    return answer;
}

회고

어려워 보였지만 그냥 구현만 하면 되는 문제였다

나는 반복문으로 했지만 부모를 재귀로 찾아가면서 수익을 더해줘도 되는 문제