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

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

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

<풀이>

1. 다단계 조직도와 판매 정보를 입력받는다.

2. 판매 이익을 자신의 추천인과 재분배하고, 각 사람들의 이익을 반환한다.

 

<해법>

1. 다단계 조직도를 정리하는 방법

=> 사람마다 자신의 추천인을 저장해놓습니다. map자료구조를 사용하여 key, value를 각각 이름으로 해놓을 수도 있습니다. 저는 실행시간 단축을 위해, 각 사람마다 인덱스(번호)를 부여하였고, 추천인 배열을 만들어서 사람의 인덱스에 추천인의 인덱스를 저장해놓는 방식으로 구현하였습니다.

 

2. 추천인과 이익을 재분배하는 방법

=> 추천인 배열을 통해 추천인이 민호가 될 때까지 이익을 재분배합니다. 저는 재귀함수를 이용하였습니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <string.h>
 
using namespace std;
 
map<string, int> m;
int parent[10000];
int profits[10000];
 
//이익 분배 함수
void divideProfit(int index, int profit) {
 
    //종료조건 : 민호까지 왔을 경우
    if (index == -1) {
        return;
    }
 
    //이익 분배
    int stolen = profit / 10;
    int myProfit = profit - stolen;
    profits[index] += myProfit;
 
    //종료조건 : 더 이상 나눌 이익이 없을 경우
    if (stolen == 0) {
        return;
    }
 
    //재귀
    divideProfit(parent[index], stolen);
}
 
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
 
    //초기화
    memset(parent, 0, sizeof(parent));
    memset(profits, 0, sizeof(profits));
 
 
    /* 해법 */
    //1. 맵 자료구조에 {'이름' : 'index'} 저장
    for (int i = 0; i < enroll.size(); i++) {
        m[enroll[i]] = i;
    }
 
    //2. 각 index마다 추천인 index 저장
    for (int i = 0; i < referral.size(); i++) {
        if (referral[i] == "-") {
            parent[i] = -1;
        }
        else {
            parent[i] = m[referral[i]];
        }
    }
 
    //3. 이익분배
    for (int i = 0; i < seller.size(); i++) {
        divideProfit(m[seller[i]], amount[i] * 100);
    }
 
    //결과 저장
    for (int i = 0; i < enroll.size(); i++) {
        answer.push_back(profits[i]);
    }
 
    //결과 반환
    return answer;
}

 

자료구조와 재귀함수에 대해 알아볼 수 있는 문제였습니다.