프로그래머스 - 다단계 칫솔(C++)

https://school.programmers.co.kr/learn/courses/30/lessons/77486

프로그래머스

 

백엔드 직무 데브 매칭 기출 문제이다. 트리를 자식부터 반대로 타고 탐색해야하기 때문에 부모가 자식의 정보를 갖고 있게 하지 않고 자식이 부모의 정보를 갖고 있도록 해야한다.

그리고 각 노드의 이름이 문자열이기 때문에 문자열을 숫자로 변환하여 map으로 관리해주었다.

 

1. 문제 조건

- 돈을 번 노드부터 시작하여 그 노드의 최상단 부모까지 타고 올라가야한다. 

- 그러면서 번 돈을 분배하는 작업을 거친다.

 

2. 내 접근

- 트리를 구성하되 벡터 형식으로 자식이 부모의 정보를 갖도록 설정하였다.

- 그리고 각 노드에서 부모가 존재하면 분배, 없으면 탐색을 종료했다.

 

3. 올바른 접근법

- 먼저  노드를 vector<int> node[1001] 이런식으로 설정할 필요가 없었다. 문제 조건을 보면 자식은 반드시 하나의 부모만 갖기 때문에 map<string , string> 으로 설정해주어도 되었다. 괜히 mapping으로 사람이름 - 번호를 진행해서 시간도 오래 걸리고 그랬던 것 같다.

- 그리고 dfs라는 명칭을 붙힌것이 맞는 건지 잘 모르겠다.

 

#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

vector<int> node[1000001]; 
map<int, int> income;
map<string, int> numbering;

void dfs(int num, int money){
    int next =  money * 10 / 100;
    //cout << next << endl;
    if(next == 0){
        income[num] += money;
        return;
    }
    
    income[num] += money - next;
    
    if(node[num].size() != 0)
        dfs(node[num][0], next);
}

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++){
        numbering.insert({enroll[i], i + 1});
        income.insert({i + 1, 0});
    }
    
    for(int i = 0; i < enroll.size(); i++){
        if(referral[i] == "-") continue;
        node[numbering[enroll[i]]].push_back(numbering[referral[i]]);
    }
    
    for(int i = 0; i < seller.size(); i++){
        dfs(numbering[seller[i]], amount[i] * 100);
        //cout << income[2] << " ";
    }

    for(int i = 1; i <= enroll.size(); i++){
        answer.push_back(income[i]);
    }
    
    return answer;
}