728x90
programmers.co.kr/learn/courses/30/lessons/77486
코딩테스트 연습 - 다단계 칫솔 판매
민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후,
programmers.co.kr
문제 풀이
import java.util.*;
public class Solution {
public class Node {
int i, c; // idx, cost
public Node( int i, int c ) {
this.i = i;
this.c = c;
}
}
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
int n = enroll.length, m = seller.length, i;
Map<String,Integer> s = new TreeMap<>(); // salesman
for( i = 0; i < n; ++i )
s.put( enroll[i], i );
s.put( "-", -1 );
int r[] = new int[n]; // referral
for( i = 0; i < n; ++i )
r[i] = s.get( referral[i] );
int p[] = new int[n]; // profit
Queue<Node> q; Node nd; int ic, in, cc, cn; // idx/cost_current/next
for( i = 0; i < m; ++i ) {
q = new ArrayDeque<>();
q.add( new Node( s.get( seller[i] ), amount[i]*100 ) );
while( !q.isEmpty() ) {
nd = q.remove();
ic = nd.i;
cc = nd.c;
in = r[ic];
cn = cc/10;
p[ic] += cc - cn;
if( in == -1 )
continue;
q.add( new Node( in, cn ) );
}
}
return p;
}
}
- enroll[] 에서 이름(String)을 key로 하고, 인덱스(int)를 value로 하는 Map 생성
ex) {-=-1, edward=2, emily=4, jaimie=5, john=0, mary=1, sam=3, tod=6, young=7}
- 각 판매원의 추천인의 인덱스를 담을 r[] ( referral ) 배열 생성
- 각 판매원의 총 수익을 담을 p[] ( profit ) 배열 생성
- seller[] 배열을 탐색하며 현재 판매원의 추천인을 찾아 올라가며 center( = "-" = -1 )가 나올 때까지 DFS
올라갈 때마다 판매원의 수익 cc ( cost_current )의 10%인 cn ( cost_next )을 뺀 값을 더한다
반응형