참고
문제해설
문제 로직고민
NOTE
•
단순 Tree구현 방식이지만, 문제에서 필요로하는 로직을 잘 살펴보자!
◦
자식노드에게 10%를 모두 받은뒤에 부모에게 10%를 받는것이 아닌, 개별적인 10%를 바로바로 올려주는 형식이다.
◦
자식노드에게 10%를 모두 받으면서 진행하면 숫자가 커지면서 10%가 1보다 커지는 경우가 생기므로 오답처리된다.
작성코드
NOTE
import java.util.*;
class Solution {
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
Map<String, Node> map = new HashMap();
map.put("minho", new Node("minho"));
for(String e : enroll){
Node n = new Node(e);
map.put(e, n);
}
for(int i=0; i<referral.length; i++){
String ref = referral[i];
Node parent;
Node child;
if(ref.equals("-")) {
parent = map.get("minho");
child = map.get(enroll[i]);
}
else{
parent = map.get(referral[i]);
child = map.get(enroll[i]);
}
parent.addChild(child);
child.setParent(parent);
}
for(int i=0; i<seller.length; i++){
String s = seller[i];
int a = amount[i];
Node node = map.get(s);
dfs(node, a*100);
}
int[] answer = new int[enroll.length];
int idx = 0;
for(String e : enroll){
answer[idx++] = map.get(e).getMoney();
}
return answer;
}
private void dfs(Node node, int money){
// 루트인 경우
if(node.getParent() == null) return;
node.giveMoney(money);
// 10%가 1원이 안되는 경우
if(money/10 < 1) return;
dfs(node.getParent(), money/10);
}
}
class Node{
private Node parent;
private List<Node> childs;
private String name;
private int money;
public Node(String name){
this.name = name;
this.childs = new ArrayList();
this.money = 0;
}
public Node getParent(){
return this.parent;
}
public List<Node> getChilds(){
return childs;
}
public int getMoney(){
return money;
}
public void setParent(Node parent){
this.parent = parent;
}
public void addChild(Node child){
this.childs.add(child);
}
public void setMoney(int money){
this.money += money;
}
public void giveMoney(int money){
if(this.parent == null) return;
int takeMoney = money/10;
money -= takeMoney;
this.money += money;
// System.out.println(this);
}
public String toString(){
return this.name + " " + this.money + " ";
}
}
Java
복사
다른사람 풀이
NOTE
import java.util.HashMap;
class Person {
String name;
Person parent;
int money;
public Person(String name, Person parent, int money) {
this.name = name;
this.parent = parent;
this.money = money;
}
void getReward(int i) {
int moneyToParent = (int) (i * 0.1);
this.money += i - moneyToParent;
if (this.parent != null)
this.parent.getReward(moneyToParent);
}
}
class Solution {
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
HashMap<String, Person> personHashMap = new HashMap<>();
for (String name : enroll)
personHashMap.put(name, new Person(name, null, 0));
for (int i = 0; i < enroll.length; i++) {
if (referral[i].equals("-"))
continue;
personHashMap.get(enroll[i]).parent = personHashMap.get(referral[i]);
}
for (int i = 0; i < seller.length; i++)
personHashMap.get(seller[i]).getReward(amount[i] * 100);
int[] result = new int[enroll.length];
for (int i = 0; i < result.length; i++)
result[i] = personHashMap.get(enroll[i]).money;
return result;
}
}
Java
복사
내가 작성한 Node를 훨씬 짧게 구현
•
Spring에서의 습관때문에 get, set함수를 모두 구현했는데 코딩테스트에서는 시간문제도 있으니 최대한 지양해야 겠다.