[Java] 프로그래머스 (다단계 칫솔 판매) Dev-Matching 3

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

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

 

Approach

트리 를 구성할 수 있는지, 특정 노드를 시작으로 부모 노드들을 순회할 수 있는지가 핵심인 문제이다.

 

문제 풀이의 주요 로직은 다음과 같다.

• 트리를 구성하는 전처리 과정이 필요하다.
  이 과정에서 트리를 구성함은 물론, 현재 노드 i에 대하여 부모 노드가 무엇인지도 저장해주어야 한다.
• 각 seller에 대하여 반복문을 돌린다.
  이 과정에서 amount를 참조하여 판매수익을 계산하고, 본인을 포함하여 추천인들에게 수익을 분배한다.

위 과정을 주어진 조건들을 만족시키면서(10원 이하는 절삭 등) 구현하면 된다.

 

Code

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashMap;

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

public class MultiStepToothbrushSales {
    static HashMap<String, Integer> map;
    static int[] parent, res;
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        init(enroll, referral);
        res = new int[enroll.length];

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

        return res;
    }

    // 판매이익 배분
    static void calculateSell(String seller, int amount) {
        int sellerIdx = map.get(seller);

        while (sellerIdx != -1) {
            int tenPercent = amount / 10;
            if (tenPercent < 1) {
                res[sellerIdx] += amount;
                break;
            } else {
                res[sellerIdx] += (amount - tenPercent);
                amount = tenPercent;
                sellerIdx = parent[sellerIdx];
            }
        }
    }

    // 구조도 초기화
    static void init(String[] enroll, String[] referral) {
        map = new HashMap<>();
        int idx = 0;
        parent = new int[enroll.length];
        Arrays.fill(parent, -1);

        // <판매자, 번호> 인덱싱
        for (int i = 0; i < enroll.length; i++) {
            map.put(enroll[i], idx++);
        }

        // 판매자 i를 추천해준 사람을 저장
        for (int i = 0; i < referral.length; i++) {
            if (referral[i].equals("-")) {
                continue;
            }
            parent[i] = map.get(referral[i]);
        }
    }

    @Test
    void test() {
        assertArrayEquals(new int[]{360, 958, 108, 0, 450, 18, 180, 1080},
                solution(new String[]{"john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"}
                        , new String[]{"-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"}
                        , new String[]{"young", "john", "tod", "emily", "mary"}
                        , new int[]{12, 4, 2, 5, 10}));
        assertArrayEquals(new int[]{0, 110, 378, 180, 270, 450, 0, 0},
                solution(new String[]{"john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"}
                        , new String[]{"-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"}
                        , new String[]{"sam", "emily", "jaimie", "edward"}
                        , new int[]{2, 3, 5, 4}));
    }
}