프로그래머스 - 다단계 칫솔 판매 문제 (자바)

programmers.co.kr/learn/courses/30/lessons/77486#

코딩테스트 연습 - 다단계 칫솔 판매

문제를 잘 읽고 방향만 잘 잡으면 쉽게 풀수 있는 문제입니다.

저는 문제를 잘 못 읽고 방향을 잘못 잡아서 고생을 좀했네요 .. 후

 

잘 읽어야하는 부분은 seller 리스트에 동일한 이름이 나올수 있다는 것입니다.

(저는 seller를 ArrayList로 만들고 index를 찾아오는 형태로 처음에 진행했어서 틀리고 있었습니다.)

 

방향은 위를 파악하면 쉽게 잡을 수 있는데 seller를 순회하면서 계산을 해야한다는 것입니다.

(저는 indegree map을 만들어서 개고생을..)

 

1. 자식 관점에서 보면 민호를 제외하고는 부모가 1개씩 존재합니다. 그래서 자신을 키로 부모를 value로하는 map을 만듭니다.

2. 앞서 이야기한 것처럼 seller에 동일한 이름을 가진 경우가 있을 수 있어서 seller 기준으로 순회하기 때문에 자신의 enroll 기준의 index을 map을 만들어서 찾을수 있게 하였습니다.

3.seller를 순회하면서 수익을 구하고 해당 수익을 분배하느 금액을 구합니다. 이때 10%가 1원 이하이면 분배하지않는다고 하였는데 int 값을 이용하면 소수점 단위를 생각하지않고 쉽게 1원미만을 제외해서 계산할수 있습니다.

4. 반복문을 통해서 부모 노드로 지속적으로 타고 들어가다가 부모가 민호인 경우("-") 멈추게 합니다.

5. 반복문 내에서 분배할 금액이 1원 미만인 경우 반목문을 탈출합니다. 

 

import java.util.*;

class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];

        Map<String, String> parentMap = new HashMap<>(); // <자신, 부모>
        Map<String, Integer> memberIndexMap = new HashMap<>(); // <자신, 자신의 순서>

        for(int i=0; i < enroll.length; i++){
            parentMap.put(enroll[i], referral[i]);
            memberIndexMap.put(enroll[i], i);
        }

        for(int i=0; i<seller.length; i++){

            String now = seller[i];
            int profit = 100 * amount[i];
            
            while(!now.equals("-")){
                int profitForParent = profit / 10; // 부모에게 넘겨줄 금액
                int nowProfit = profit - profitForParent; // 자신이 가져갈 금액

                // 자신의 index에 금액만큼 더함
                answer[memberIndexMap.get(now)] += nowProfit;

                // 노드는 부모로 이동하면서 수익을 부모에게 넘겨준 금액으로 초기화
                now = parentMap.get(now);
                profit /= 10;

                // 10%의 금액이 1원 미만인 경우
                if (profit < 1) {
                    break;
                }
            }
        }

        return answer;
    }
}

아래 코드는 Person이라는 객체를 만들고 해당 객체 내에 재귀함수를 통해서 계산하여서 해결하였습니다.

// 프로그래머스 다단계 칫솔 판매 문제
import java.util.HashMap;

class Person {
    String name;
    Person parent;
    int profit;

    public Person(String name, Person parent, int profit) {
        this.name = name;
        this.parent = parent;
        this.profit = profit;
    }

    public void CalcProfit(int profit) {
        int profitToParent = profit / 10;
        this.profit += profit - profitToParent;
        if (this.parent != null && profitToParent >= 1) {
            this.parent.CalcProfit(profitToParent);
        }
    }
}

class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        HashMap<String, Person> personMap = new HashMap<>();
        for (String name : enroll) {
            personMap.put(name, new Person(name, null, 0));
        }

        for (int i = 0; i < enroll.length; i++) {
            if (referral[i].equals("-")) {
                continue;
            }
            personMap.get(enroll[i]).parent = personMap.get(referral[i]);
        }

        for (int i = 0; i < seller.length; i++) {
            personMap.get(seller[i]).CalcProfit(amount[i] * 100);
        }

        int[] result = new int[enroll.length];

        for (int i = 0; i < result.length; i++) {
            result[i] = personMap.get(enroll[i]).profit;
        }

        return result;
    }
}