프로그래머스 - 다단계 칫솔 판매(Java)

역추적 문제입니다.

https://ksb-dev.tistory.com/109 에 역추적 문제 예제가 있으니 역추적을 잘 모르시는 분은 한 번 읽어보시기 바랍니다.

 

역추적의 기본 개념은 간단합니다.

배열에 부모의 위치를 저장하여 재귀적으로 부모를 찾아가는 방법입니다.

private static int find(int po) {
    if(parents[po] == po){
        return po;
    }
    return find(parents[po]);
}

 

어디선가 많이 본 코드 아닌가요?

네, 유니온-파인드(Union-Find)에서의 그 파인드 입니다.

https://ksb-dev.tistory.com/114 에 유니온 파인드를 잘 정리해 놨으니 잘 모르시는 분은 읽어보시기 바랍니다.

 

파인드를 사용하기 위해서는 기본적으로 부모의 위치와 자신의 위치의 숫자가 필요합니다.

문제에서 딱히 나와있지는 않지만, 중복된 이름이 없다고 가정하여 map을 사용하고 각 이름에 숫자를 부여했습니다.

map을 사용하면 O(1)의 시간 복잡도로 get을 할 수 있습니다.

또, find 연산을 위해 자기 자신의 위치를 배열에 저장했습니다.

for (int i = 0; i < enroll.length; i++) {
    map.put(enroll[i], i+1);
    parents[i] = i;
}

 

문제에서 referral은 자기 자신의 부모를 의미합니다.

map에서 이름을 통해 부모 위치를 가져옵니다.

단, "-"는 아무도 추천하지 않았지만 그림에서 알 수 있듯이 Center의 자식이므로 최상위 위치인 0을 저장합니다.

(0의 위치는 민호. 즉, Center을 의미합니다.)

for (int i = 0; i < referral.length; i++) {
    String s = referral[i];

    if (s.equals("-")) {
        parents[i+1] = 0;
    } else {
        parents[i+1] = map.get(s);
    }
}

 

seller와 amount를 통해 판매자와 판매 개수를 통해 부모를 역추적합니다.

find를 하여 부모를 재귀적으로 찾아가고 부모에게 줄 값을 전달합니다.

주의해야 할 점은 올림(ceil)연산을 통해야 1의 자리 계산이 제대로 동작합니다.

private static int find(int po, int mo) {
    if(parents[po] == po){
        return po;
    }
    money[po-1] += Math.ceil(mo*0.9);
    return find(parents[po], (int)(mo*0.1));
}

money[po-1]을 하는 이유는 money배열에 민호(Center)가 포함되지 않기 때문입니다.

문제의 결과는 민호를 제외한 사람들이 얻는 금액을 요구하기 때문입니다.

 

[구현 코드]

import java.util.HashMap;
import java.util.Map;

class Solution {
    private static Map<String, Integer> map;
    private static int[] parents, money;

    public static int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        map = new HashMap<>();
        parents = new int[enroll.length + 1];
        money = new int[enroll.length];

        for (int i = 0; i < enroll.length; i++) {
            map.put(enroll[i], i+1);
            parents[i] = i;
        }

        for (int i = 0; i < referral.length; i++) {
            String s = referral[i];

            if (s.equals("-")) {
                parents[i+1] = 0;
            } else {
                parents[i+1] = map.get(s);
            }
        }

        for (int i = 0; i < seller.length; i++) {
            String person = seller[i];
            int po = map.get(person);
            int mo = amount[i] * 100;

            find(po, mo);
        }

        return money;
    }

    private static int find(int po, int mo) {
        if(parents[po] == po){
            return po;
        }
        money[po-1] += Math.ceil(mo*0.9);
        return find(parents[po], (int)(mo*0.1));
    }
}