[C++] 프로그래머스 다단계 칫솔 판매 풀이

 

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

코딩테스트 연습 - 다단계 칫솔 판매

이 문제는 읽어보면 아주 간단한 문제이다. 문제를 읽고 DFS방식으로 풀면 금방 풀릴 것이라는 생각이 바로 들 것이다. 다단계에서 판매하는 칫솔의 수익의 10퍼센트를 자신을 추천한 사람에게 줄 때 사람들의 수익을 구하는 문제이다. 코드는 다음과 같다.

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

map<string,string> graph; //누구에게 추천받았는지를 저장
map<string, int> cost; //각 사람이 번 돈을 저장할 map

void dfs(string now, int amount) { //현재 사람이 번 돈
    string ref = graph[now]; //추천인이 누군지 찾음
    int nxt = amount / 10; //10퍼센트 떼서
    if(ref == "-") { //center를 만날 경우
        cost[now] += (amount - nxt); //자기 자신은 10퍼센트를 떼고 얻음
        return;
    }
    else { //추천인이 center가 아닌 경우
        int nxt = amount / 10; //10퍼센트를 떼서
        cost[now] += (amount - nxt);  //자기 자신은 나머지를 갖고
        if(nxt == 0) return; //만약 10퍼센트가 1원도 안나올 경우 dfs 멈춤
        dfs(ref, nxt); //추천인에게 줄 돈이 남은 경우 추천인의 추천인 계속 탐색
    }
}

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++) { //모든 사람에 대하여
        graph[enroll[i]] = referral[i]; //자신을 추천한 사람 map으로 연결
    }
    
    for(int i = 0; i < seller.size(); i++) { //판매한 사람 모두 dfs로 추천인에게 10퍼센트씩 부여
        dfs(seller[i], amount[i] * 100); //칫솔 1개에 100원이므로 판매 수에 100을 곱한다
    }
    
    for(int i = 0; i < enroll.size(); i++) {
        if(cost.find(enroll[i]) == cost.end()) //만약 수익이 없는 사람을 발견할 경우
            answer.push_back(0); //0원 push_back
        else
            answer.push_back(cost[enroll[i]]); //map에 저장한 수익 push_back
    }

    return answer;
}

    DFS를 이용하여 자신의 추천인에게 10퍼센트를 계속 떼어 주는 것이다. 만약 현재 돈이 10원 미만이어서 10퍼센트를 떼었을 경우 1원도 나오지 않을 경우 DFS를 빠져나오게 된다. 저 조건을 뺄 경우 몇몇 테스트 케이스에서 시간초과가 발생한다. 불필요한 탐색을 거르는 장치인 것이다.

 

    그래프와 각 사람이 번 돈들을 map으로 표현하는 것이 핵심이었다. 다른 표현 방법으로 각 사람을 인덱스 번호로 표현하여 각각 사람의 인덱스를 가지고 있고 찾아봐야할텐데 map을 이용하여 그러한 시간을 줄이고 더 편하게 이름으로 사람을 찾을 수 있었다.

 

    문제의 설명이 길어 긴장했지만 읽어보니 굉장히 단순하게 풀 수 있는 방법이었다. DFS 재귀 방식 말고도 while문을 이용하여 더 빠른 시간에 풀 수 있는 방법도 있으니 그 방법도 생각해보면 좋을 것 같다.