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

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

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : 트리, 해시맵 
풀이 시간 : 33분 

문제 풀이 

일단 문제가 꽤 길다. 

문제를 읽어보면 어떤 직원이 판매한 칫솔의 수익에서 10%만큼 직원의 추천인(트리의 부모)에게 전달되고, 이 구조가 재귀적으로 반복되고 있음을 알 수 있다.

문제를 풀며 주의해야 할 점은 수익을 나누는 방법인데, 돈을 받은 직원은 받은 돈의 10%를 추천인 직원에게 넘기고, 나머지를 자기가 갖게 되는 것이다. 다시 말해서 돈의 10%를 먼저 계산해 준 뒤, 현재 돈에서 계산된 10%를 빼주어야 한다.

// 이런 식으로 계산이 이루어져야한다.
answer[u] += money - (money * 10 / 100);
money = money * 10 / 100;


// 이렇게 계산하면 절대 안된다.
answer[u] += money * 90 / 100;
money = money * 10 / 100;

문제를 푼 순서는 다음과 같다.

우선, 문자열 타입으로 입력되는 직원을 `map`을 사용하여 역으로 정점 매칭시켜 주었다.

이후, 판매 수익이 들어올 때마다 bfs를 진행해주어 다단계 업데이트를 수행해주었다.

 

+ 이렇게 풀어도 맞긴 했다. 근데 문제를 풀고 다시 생각해 보니 부모 노드는 유일한데 굳이 bfs를 돌릴 필요가 있나 싶었다. 풀이를 따로 진행하지는 않았지만, 부모와 자식을 `map`으로 한 번 더 연결시켜 준 뒤, 재귀적으로 위로 올라가도 괜찮았을 것 같다. 그러면 시간복잡도는 비슷하겠지만, 그래프를 만들어줄 필요가 없게 된다. 이 글을 보는 여러분이 한 번 시도해 보도록 :)

 

코드

/*
ㄹㅇ 다단계
풀이:
1. 회원 이름을 쿼리로 저장한 다음, 그래프 생성
2. seller 돌면서 번 돈 업데이트
*/

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

map<string, int> company;

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer(enroll.size());
    // init
    vector<vector<int>> tree(enroll.size());
    for (int i=0;i<enroll.size();i++){
        company.insert({enroll[i], i});
    }
    for (int i=0;i<referral.size();i++){
        if (referral[i] == "-") continue;
        tree[company[enroll[i]]].push_back(company[referral[i]]);
    }
    
    // 판매 시작
    for (int i=0;i<seller.size();i++) {
        int money = amount[i] * 100;
        int u = company[seller[i]];
        queue<pair<int, int>> q;
        q.push({u, money});
        while (!q.empty()){
            u = q.front().first;
            int money = q.front().second;
            q.pop();
            if (!money) break;
            
            // 현재 녀석 머니 업데이트
            answer[u] += money - (money * 10 / 100);
            money = money * 10 / 100;
            for (int v=0;v<tree[u].size();v++){
				q.push({ tree[u][v], money });
            }
        }
        // for (int k=0;k<answer.size();k++){
        //     cout << answer[k] << ' ';
        // }
        // cout << '\n';
    }

    
    return answer;
}

배운 점 

입력의 개수가 매우 많은데, 무언가 매칭을 해야하는 문제다 싶으면 맵을 사용하는 것이 좋아보인다. 

 

`map` 라이브러리를 사용하며 `hashmap`과 차이점이 궁금했는데, 이번 기회에 검색해보니 map은 BST를 사용하여 저장하기 때문에 자료가 key를 기준으로 정렬되어 보관된다는 점이 있고, hashmap은 해시테이블로 자료가 저장되기에 정렬되지 않는다는 차이점이 있다. 또한, 이 과정에서 시간복잡도의 차이가 존재하는데 map은 $O(logn)$이 걸리고, hashmap은 $O(1)$이 걸린다.

따라서, 삽입 검색 삭제가 매우 자주 필요한 경우에는 `hashmap`을 사용하는 것이 좋아보이고, 정렬이 필요한 경우에는 `map`을 사용하자 ~!