[ 프로그래머스 다단계 칫솔 판매 (Lv3) ] (C++)

프로그래머스의 다단계 칫솔 판매 (Lv3) 문제이다.

 

[ 문제풀이 ]

조직원들의 관계가 주어졌을 때, 칫솔을 판매했을 때의 이익금을 각각 얼마씩 가져갈 수 있는지를 구해야 하는 문제이다.

문제를 어떻게 접근할지 접근과정부터, 정답을 도출하는 과정까지 단계별로 진행해보자.

 

#1. 판매원의 이름 관리

주어진 문제를 보면, 판매원들이 모두 string형의 데이터로 주어지게 된다.

그리고 우리는 이 string을 토대로, 해당 판매원을 조직에 참여시킨 사람의 관계를 파악해야 한다.

본인은 이 과정을 위해서 string을 모두 int형으로 매핑시켜 주는 과정을 진행해 주었다.

이 과정에서 자료구조 map을 사용하였다. map<string , int> 로 선언을 해서, 모든 사람들의 이름을 int형으로 관리를 해 주었다. 이 과정을 코드로 나타내면 다음과 같다.

void Mapping_String_To_Int(vector<string> List, map<string, int> &MAP)
{
	int Num = 1;
	for (int i = 0; i < List.size(); i++)
	{
		string S = List[i];
		MAP[S] = Num++;
	}
}

위의 코드에서, 'List'라는 매개변수는, 문제에서 주어지는 매개변수 'enroll'을 의미한다.

우리는 위의 과정을 통해서 모든 판매원의 이름을 간단하게 int형으로 관리를 할 수 있게 될 것이다.

 

#2. 부모와 자식 관계로 표현

이 문제에서는, 판매원과 판매원을 조직에 참여시킨 또 다른 판매원의 관계가 주어진다.

그리고 이 관계에 따라서 판매 이익금을 나눠 가져야 하는 형태이다.

간단하게 트리 구조로 이를 생각해본다면, 노드의 자식과 부모 관계로 표현할 수 있고 이 관계를 파악해야 한다.

본인은 이를 위해 하나의 변수를 만들어 주었다.

int Parent[] 라는 배열이다. (실제 코드에서는, 벡터를 이용해서 이를 만들어 주었다.)

Parent[A] = B의 의미는, "A의 부모, 즉, A를 조직에 참여시킨 판매원은 B입니다." 를 의미한다.

#1의 과정에서 우리는 문자열을 int형으로 관리할 수 있도록 만들어 놓았기 때문에, 이를 쉽게 표현할 수 있다.

코드로 나타내면 다음과 같다.

void Make_Parent(vector<string> enroll, vector<string> referral, map<string, int> MAP, vector<int>& Parent)
{
	for (int i = 0; i < enroll.size(); i++)
	{
		string Child = enroll[i];
		int I_Child = MAP[Child];

		string Par = referral[i];
		if (Par == "-")	Parent[I_Child] = 0;
		else
		{
			int I_Par = MAP[Par];
			Parent[I_Child] = I_Par;
		}
	}
}

 

#3. 판매 이익금 계산

한 사람이 칫솔을 판매하게 되면, 해당 사람을 조직에 참여시킨 사람에게, 그리고 그 사람을 또 조직에 참여시킨 사람에게 계속해서 올라가면서 이익금을 분배하는 과정을 구현해야 한다.

본인은 이 과정을 재귀를 통해서 구현하였다.

재귀를 통해서 자신의 부모가 없을 때 까지 계속해서 판매 이익금을 나눠가도록 만들어 주었다.

void DFS(int Cur, int Cost, vector<int> Parent, vector<int> &Money)
{
	if (Cur == 0) return;
	
	int Give_Cost = Cost / 10;
	if (Give_Cost < 1)
	{
		Money[Cur] += Cost;
		return;
	}
	else
	{
		int My_Cost = Cost - Give_Cost;
		Money[Cur] += My_Cost;
		DFS(Parent[Cur], Give_Cost, Parent, Money);
	}
}

코드로 표현하면 위와 같이 표현을 할 수 있다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <map>
using namespace std;
 
 
void Mapping_String_To_Int(vector<string> List, map<string, int> &MAP)
{
    int Num = 1;
    for (int i = 0; i < List.size(); i++)
    {
        string S = List[i];
        MAP[S] = Num++;
    }
}
 
void Make_Parent(vector<string> enroll, vector<string> referral, map<string, int> MAP, vector<int>& Parent)
{
    for (int i = 0; i < enroll.size(); i++)
    {
        string Child = enroll[i];
        int I_Child = MAP[Child];
 
        string Par = referral[i];
        if (Par == "-")    Parent[I_Child] = 0;
        else
        {
            int I_Par = MAP[Par];
            Parent[I_Child] = I_Par;
        }
    }
}
 
void DFS(int Cur, int Cost, vector<int> Parent, vector<int> &Money)
{
    if (Cur == 0) return;
    
    int Give_Cost = Cost / 10;
    if (Give_Cost < 1)
    {
        Money[Cur] += Cost;
        return;
    }
    else
    {
        int My_Cost = Cost - Give_Cost;
        Money[Cur] += My_Cost;
        DFS(Parent[Cur], Give_Cost, Parent, Money);
    }
}
 
void Calculate(map<string, int> MAP, vector<int> Parent, vector<string> Seller, vector<int> Amount, vector<int> &Money)
{
    for (int i = 0; i < Seller.size(); i++)
    {
        string S_Seller = Seller[i];
        int I_Seller = MAP[S_Seller];
        int Cost = Amount[i] * 100;
 
        DFS(I_Seller, Cost, Parent, Money);
    }
}
 
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) 
{
    vector<int> answer;
    
    map<string, int> Mapping;
    Mapping_String_To_Int(enroll, Mapping);
 
    vector<int> Parent(enroll.size() + 1);
    Make_Parent(enroll, referral, Mapping, Parent);
 
    vector<int> Money(enroll.size() + 1, 0);
    Calculate(Mapping, Parent, seller, amount, Money);
 
    for (int i = 1; i <= enroll.size(); i++) answer.push_back(Money[i]);
    return answer;
}