728x90
programmers.co.kr/learn/courses/30/lessons/77486
풀이
처음에는 트리 구조로 구현해야 하나 싶었지만, Person 객체를 정의하고 해시맵을 사용하여 간단하게 추천인 관계를 추적할 수 있도록 구현했다.
1) enroll과 referral로부터 정보를 가져와 people 해시맵을 채워넣고 추천인 관계 설정
2) 이익 배분
2-1) seller와 amount의 길이만큼 이익 배분 반복 시행
2-2) while문에서 추천인에게 더이상 이익을 배분할 수 없을 때까지 반복하여 이익을 배분
3) answer에 이익 결과값 담기
코드
import java.util.*;
class Solution {
class Person {
String name;
int profit;
String parent;
public Person(String name){
this.name = name;
this.profit = 0;
this.parent = null;
}
}
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
int[] answer = new int[enroll.length];
// key : 이름(String) , value : Person 객체
HashMap<String, Person> people = new HashMap<>();
// people에 민호 추가
people.put("-",new Person("-"));
// people에 나머지 사람들 추가
for(int i = 0; i < enroll.length; i++){
people.put(enroll[i], new Person(enroll[i]));
people.get(enroll[i]).parent = referral[i]; // parent 관계 설정
}
// 이익 배분
for(int i = 0; i < seller.length; i++){
// 추천인에게 이익 배분
String now = seller[i];
int now_profit = 100 * amount[i]; // 현재 받을 수 있는 이익
int next_profit = 0; // 다음 추천인이 받을 수 있는 이익
while(true){
// 추천인에게 10%로 넘겨줄 금액이 안되거나, 추천인이 없으면 해당 이익 배분 종료
if(now_profit < 10 || people.get(now).parent == null) {
people.get(now).profit += now_profit;
break;
}
// 추천인에게 가는 이익 = 현재의 10% (원 단위 절사)
next_profit = now_profit / 10;
// 현재 받을 수 있는 이익 = 원래 받을 수 있는 이익 - 추천인에게 가는 이익
people.get(now).profit += now_profit - next_profit;
// 추천인으로 now의 포인터 변경
now = people.get(now).parent;
// now_profit 변경
now_profit = next_profit;
}
}
// answer에 각각의 이익 담기
for(int i = 0; i < enroll.length; i++){
answer[i] = people.get(enroll[i]).profit;
}
return answer;
}
}
'Programming > 코딩테스트 준비' 카테고리의 다른 글
[프로그래머스] 전력망을 둘로 나누기 (위클리 챌린지 9주차 문제) (Python) (0) | 2021.10.06 |
---|---|
[프로그래머스] 조이스틱 (Java) (0) | 2021.05.08 |
[프로그래머스] 헤비 유저가 소유한 장소 (MySQL) (0) | 2021.05.08 |
[프로그래머스] 행렬 테두리 회전하기 (0) | 2021.05.08 |
[프로그래머스] 로또의 최고 순위와 최저 순위 (0) | 2021.05.08 |