문제
칫솔을 판매하는데 다단계 방식이다. 내가 추천한 사람이 칫솔을 판매하면 나에게 수익의 10%가 들어온다. 만약 내가 누군가의 추천으로 들어왔다면 나의 추천인에게 금액의 10%을 주어야 한다. 추천받지 않고 들어온 사람이거나 금액이 1원 이하라면 금액 전달을 멈춘다.
풀이
처음 문제를 읽고 재귀로 풀어야 겠다는 생각이 들었다. 문제는 어떤 어떤 자료구조를 사용해서 판매인들과 금액을 담아야 하는지 였다. 만족해야 하는 것은 판매원이 자신을 추천한 사람의 이름을 담고 있어야 한다는 것이다. 그래야 재귀를 통해 타고 올라가서 금액을 계산할 수 있다.
처음엔 인접리스트 방식으로 그래프를 입력받았던 것을 떠올려 vector<vector<"string">> 으로 시도했다가 실패했다. 직원이름으로 접근이 불가능했다. 다음으로 map을 사용했다. 정렬할 필요가 없으니 unordered_map을 사용했다.
unordered_map<string, string> 으로 {본인,자신을 추천한 사람} 을 입력받고
입력으로 들어오는 판매한 사람과 판매액을 매개변수로 재귀함수에 넘겨준다.
재귀함수 code // 부모의 이름이 none이면 더이상 금액을 전달하지 않음(재귀가 멈춤)
void getMoney(string name, int amount) { if (parent[name] == "none") { int left_money = amount * 0.1; money[name] += amount - left_money; return; } else { int left_money = amount * 0.1; money[name] += amount - left_money; if (left_money < 1) return; getMoney(parent[name], left_money); } }
코드
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
unordered_map<string, string> parent;
unordered_map<string, int> money;
void getMoney(string name, int amount) {
if (parent[name] == "none") {
int left_money = amount * 0.1;
money[name] += amount - left_money;
return;
}
else {
int left_money = amount * 0.1;
money[name] += amount - left_money;
if (left_money < 1) return;
getMoney(parent[name], left_money);
}
}
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++) {
if (referral[i] == "-") parent.insert({ enroll[i],"none" });
else parent.insert({ enroll[i],referral[i] });
}
for (int i = 0; i < seller.size(); i++) {
getMoney(seller[i], amount[i] * 100);
}
for (int i = 0; i < enroll.size(); i++) {
answer.push_back(money[enroll[i]]);
}
return answer;
}
}고찰
이전까지 map을 사용해본 적이 없었는데 이번 기회에 익혀놓아야 겠다.
map은 key-value 값으로 이루어진 자료구조이고 c++ stl 내부에는 RB트리로 구성되어있다고한다. 기본적인 map의 경우는 key값을 기준으로 값이 들어올 때 마다 자동으로 정렬을 실시한다.
그냥 map과 unordered_map에는 각각 RB기반, hash Table을 기반으로 하기 때문에 탐색속도에서 O(logN) 과 O(1)의 차이를 가집니다. 정렬의 필요성이 없다면 그냥 ordered_map을 사용하면 된다.
map은 보통 key 와 value로 이루어진 데이터를 저장하고 다룰 때 사용된다. ex) 성 과 이름
간단한 메서드에 대해 알아보자
선언 map<string,int> m;
삽입 m.insert({"price",300}) / m[price] = 300;
탐색 m.find("price") // 못찾았다면 m.end() 를 반환한다.
접근 for(auto iter=m.begin(); iter<b.end(); iter++){
cout << iter->first << " " << iter->second << endl;
}
m["price"] 를 통해 value값 300에도 접근이 가능
삭제 m.erase("price") / m.erase(m.begin()+2)
m.erase(m.begin(),m.end()) / m.clear() //모든 요소 삭제
