프로그래머스: 다단계 칫솔 [JAVA]

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/77486

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

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 enroll, referral 배열을 한 번에 돌며 이름을 인덱스화, 해당 이름(노드)의 상위 노드를 저장
2. 이후 주어진 seller, amount 배열을 돌며 나누어 가질 이익금을 계산 후 누적

 문제에서도 예시로 보여진 것처럼 우선 문제 해결을 위해선 주어진 데이터들을 가지고 트리를 구성할 수 있어야 하며, 문제 해결 흐름 상 트리의 말단에서 루트로 거슬러 올라가야 하기 때문에 각 노드의 부모 노드가 누구인지를 저장하는 방식으로 구현하면 된다. 이 때 주어진 이름들 자체를 활용하기엔 제약이 크기 때문에, HashMap<String, Integer>을 통해 이름을 하나의 인덱스로 변환해주면 이후 쉽게 처리할 수 있다.

 그렇게 이름의 인덱스화, 부모 노드 인덱스 저장의 전처리 과정을 거치고 나서는, seller와 amount 배열을 통해 이익금을 계산해야 한다. 이 경우 하나의 이익금에 대해 노드를 거슬러 올라가며 계산하기 때문에, 하나의 과정에서 루트 노드 전까지 문제에서 요구하는 대로 자신의 부모 노드로 이익금의 10%를 전달, 그 나머지를 자신의 이익으로 누적하는 과정을 함수로 작성했다. 

 

class Solution {
    int[] answer, parent;

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        int index = 1;
        answer = new int[enroll.length];
        parent = new int[enroll.length + 1];

        hashMap.put("-", 0);

        for (int i = 0; i < enroll.length; i++) {//이름 인덱스화, 부모 노드 저장
            hashMap.put(enroll[i], index++);
            parent[i + 1] = hashMap.get(referral[i]);
        }

        for (int i = 0; i < seller.length; i++) {//이익금 계산
            calculate(hashMap.get(seller[i]), amount[i] * 100);
        }
        
        return answer;
    }

    void calculate(int seller, int profit) {
        int person = seller, price = profit;

        while (person!=0) {//루트 노드가 아니라면
            int remain = price / 10;
            int quotient = price - remain;

            answer[person - 1] += quotient;//값 누적

            if (remain == 0) {//더 이상 나눌 금액이 없으면
                break;
            } else {
                person = parent[person];
                price = remain;
            }
        }
    }
}

결과