코딩테스트 연습 - 다단계 칫솔 판매
민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후,
programmers.co.kr
문제 설명
민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.
민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10% 까지 자신에 이익이 됩니다. 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.
예를 들어, 아래와 같은 판매 기록이 있다고 가정하겠습니다. 칫솔의 판매에서 발생하는 이익은 개당 100 원으로 정해져 있습니다.
판매원판매 수량이익금| young | 12 | 1,200 원 |
| john | 4 | 400 원 |
| tod | 2 | 200 원 |
| emily | 5 | 500 원 |
| mary | 10 | 1,000 원 |
요약하면 다단계 직원들이 물건을 팔아 이익이 생기면 직속상사에게 10퍼센트의 수수료를 상납하고
그 위에사람이 10퍼센트 들고가고 들고가는 반복적인 피라미드를 만드는 문제!
저는 서로 이어져 있다는 점에서 바로 그래프로 만들어 풀려고 했습니다!
그러나 실패......
너무 긴 코드...
코드가 많이 길어졌네요... 아마 이코드에선 수익금의10퍼센트 계산이 2칸위로 올라가질 않는것 같습니다...
설계오류!
#include <string>
#include <vector>
#include <iostream>
#define max 10000
using namespace std;
int find(vector<string> arr,string s){//인덱스 계산
int count=0;
for(string i : arr){
if(i==s){
return count;
}
count+=1;
}
return 0;
}
int upmem(int uplist[][max],int size,int a){//상사 찾기
for(int i=0;i<size;i++){
if(uplist[a][i]==1){
return i;
}
}
return max+1;
}
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
vector<int> answer;
int uplist[max][max]={0};
int input1[max]={0};//번돈의 90퍼
int input2[max][max]={0};//10퍼센트 받은 돈
for(int i=0;i<referral.size();i++){//윗단 기록
if(referral[i]!="-"){
uplist[i][find(enroll,referral[i])]=1;
}
}
for(int i=0;i<seller.size();i++){//자신이 번돈 + 윗상사들에게 전달
input1[find(enroll,seller[i])]+=amount[i]*90;
int superior=upmem(uplist,enroll.size(),find(enroll,seller[i]));//바로윗상사
if(superior!=10001){//타고 올라가기!
input2[superior][i]+=amount[i]*10;//상사에게 i가
//cout<<enroll[i]<<"|"<<enroll[superior]<<endl;
int memo=input2[superior][i];//준금액
int me =i;//하
int memoindex=superior;//상
while(true){
memoindex=superior;
superior=upmem(uplist,enroll.size(),superior);
if(superior==10001 and input2[superior][memoindex]<10){
break;
}
else if(superior==10001 and input2[superior][memoindex]>=10){
input2[memoindex][i]-=memo/10;
}
else{
input2[memoindex][i]-=memo/10;
input2[superior][memoindex]+=memo/10;
}
me=memoindex;
}
}
}
for(int i=0;i<enroll.size();i++){
int sum=0;
for(int j=0;j<enroll.size();j++){
if(input2[i][j]<10){
sum+=input2[i][j];
}
else{
sum+=input2[i][j]-input2[i][j]/10;
}
}
input1[i]+=sum;
}
for(int i=0;i<enroll.size();i++){//출력
for(int j=0;j<enroll.size();j++){
cout<<input2[i][j]<<",";
}
cout<<endl;
answer.push_back(input1[i]);
}
return answer;
}
그 다음은 값을 받는 즉시 최상단까지 계산하며 이동하는 함수를 만들어 보았습니다...
그러나 이것 또한 실패......
아까 보단 코드길이가 많이 줄었지만 한사람이 한건의 수익을 달성하는 것이 아니더라구요...
만약 A가 1원을 벌고 9원을 벌었을때 밑의 코드대로 했을때 10보다 작아 수수료가 안붙는데
전체적으로 보았을때 총 10원을 벌어 수수료 1원이 발생하네요.... ㅋㅋ 이걸 생각.. 못했네요
많이 줄어든 코드!
#include <string>
#include <vector>
#include <iostream>
#define max 10000
using namespace std;
int find(vector<string> arr,string s){//인덱스 계산
int count=0;
for(string i : arr){
if(i==s){
return count;
}
count+=1;
}
return 0;
}
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {//다시해야할듯 값하나 받아서 바로 위까지 올리는 그런거 ㅇㅇ
vector<int> answer;
int memlist[max]={0};//직속상사 리스트
int money[max]={0};
for(int j=0;j<enroll.size();j++){// 관계설정
if(referral[j]!="-"){
memlist[j]=find(enroll,referral[j]);
}
else{
memlist[j]=-1;
}
}
for(int i=0;i<seller.size();i++){// 금액청산
int member=find(enroll,seller[i]);// 머니를 받은 사람 인덱스
int gold=amount[i]*100;// 현재 받은돈
int nextmember=10001;//다음사람
money[member]+=gold;//월급수령
while(true){
nextmember=memlist[member];//다음사람 찾기
if(gold>10){//10넘고
gold=gold/10;
money[member]-=gold;
if(nextmember!=-1){// 다음사람이 있다!
money[nextmember]+=gold;
member=nextmember;
}
else{//없음...
break;
}
}
else{//넘겨줄 돈 부족
break;
}
}
}
for(int j=0;j<enroll.size();j++){//출력
answer.push_back(money[j]);
}
return answer;
}
결국 서칭해서 풀었습니다... 허탈하네요
일단 많은 분들이 map을 사용해서 풀었네요 (저는 일일이 인덱스값을 찾아갔지만 이렇게 풀면 더쉽네요..)
map<string, int> mres;// 수익
map<string, string> mref;// 직속상사 맵
vector<int> answer;
그리고 수익금을 계산하는부분! ... 짧네요;;
void distribute(string seller, int money) {
if(seller=="-") return;// 최상단
int part = money*0.1;// 수수료계산
mres[seller]+=money-part;// 판매원 수익계산
if(part){
distribute(mref[seller], part);// 재귀로 올라가기
}
}
메인부분
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
for(int i=0;i<enroll.size();i++){// 수익금초기화, 직속상사 입력
mres[enroll[i]]=0;
mref[enroll[i]]=referral[i];
}
for(int i=0;i<seller.size();i++){// 모든 판매원 수익계산부분
distribute(seller[i], amount[i]*100);
}
for(int i=0;i<mres.size();i++){// answer로 값 전달
answer.push_back(mres[enroll[i]]);
}
return answer;
}for문 3개로 끝나네요... ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
아
넵... 정신차리고 더 열심히 공부하겠습니다.
*all
#include <vector>
#include <map>
using namespace std;
map<string, int> mres;
map<string, string> mref;
vector<int> answer;
void distribute(string seller, int money) {
if(seller=="-") return;
int part = money*0.1;
mres[seller]+=money-part;
if(part) distribute(mref[seller], part);
}
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
for(int i=0;i<enroll.size();i++){
mres[enroll[i]]=0;
mref[enroll[i]]=referral[i];
}
for(int i=0;i<seller.size();i++){
distribute(seller[i], amount[i]*100);
}
for(int i=0;i<mres.size();i++){
answer.push_back(mres[enroll[i]]);
}
return answer;
}
틀린 점이 있다면 댓 달아주세요!
'코딩테스트!(프로그래머스 & 백준) > 프로그래머스-C++' 카테고리의 다른 글
| 코딩테스트 -- [1차] 셔틀버스 - (프로그래머스 / C++) (0) | 2022.07.03 |
|---|---|
| 코딩테스트 -- 자물쇠와 열쇠 - (프로그래머스 / C++) (0) | 2022.07.02 |
| 코딩테스트 -- 순위 - (프로그래머스 / C++) (0) | 2022.06.29 |
| 코딩테스트 -- 디스크 컨트롤러- (프로그래머스 / C++) (0) | 2022.06.28 |
| 코딩테스트 -- 입국심사 (프로그래머스 / c++) / (이분탐색) (0) | 2022.06.26 |
댓글