1,2,3 떨어트리기

https://school.programmers.co.kr/learn/courses/30/lessons/150364

프로그래머스

주어진 트리에서 1, 2, 3 의 공을 내려보내 각 노드가 원하는 값을 갖는 공의 순서를 찾는 문제입니다.

 

트리를 만드는 과정은 DS 를 구현해서 진행했습니다.

이후 트리의 각 노드에서 순서가 변경되는 로직이 있고 이 부분도 노드 구현에 반영한 flow 함수를 구현했습니다.

 

처음에는 공의 경우의 수를 따라가며 backtracking ( 가지치기 ) 로 접근했는데 몇몇 케이스에서 "시간 초과" 가 발생하여 비용을 줄일 수 있는 방법을 고민했습니다.

 

아이디어는 다음과 같습니다.

1. 공을 내려보내는 로직은 변경할 수 없다

2. 공을 내려보내면서 최소한의 공을 내리는 케이스를 찾는다

이는 각 leaf node 에서 공의 갯수를 세면서 target 에 도달 가능한 경우를 찾았습니다 ( 가지 치기 )

예를 들어 leaf node 의 공의 갯수가 target 의 갯수보다 큰 경우 공의 갯수에 최소 공의 값 ( 1 ) 을 대입해도 결국 target 의 값을 넘기 때문에 답이 될 수 없습니다. 이런 상황에 도달한다면 이미 이전의 상태는 답이 될 수 없으니 ( small case ) 앞으로 공을 던져도 답을 해결할 수 없어 답을 풀 수 없는 상황 입니다 ( -1 )

 

점화식으로는 현재 상태에서 각 leaf node 의 공의 갯수에 공의 최대 값 ( 3 ) 을 곱했을 때 target 값을 넘어선다면 해당 leaf node 는 target 을 만족할 수 있는 상황이기에 Satisfied 상태를 부여하고 각 leaf node 가 모두 Satisfied 상태라면 현재 공의 갯수에서 답을 찾을 수 있다고 판단합니다.

 

이후에는 각 leaf node 에 도달한 공의 값을 결정하면 되는데 공의 값을 오름차순으로 만들어야 합니다.

이 때는 만족하는 현재 공의 상태를 indexer ( 배열 ) 로 만들고 특정 leaf node 에 도달 가능한 map 을 구성한 다음 map 의 값 ( 동일 leaf node 의 index ) 를 기준으로 특정 값을 특정 갯수로 만드는 방법을 찾으면 됩니다 ( 오름차순 )

 

이는 배열에 최소 값 ( 1 ) 을 설정한 상태에서 배열의 모든 구성이 target 값이 될 때까지 배열의 끝부터 가장 큰 값 ( 3 ) 을 채워 넣으면 됩니다. 이렇게 찾은 배열은 leaf node 가 target 값을 만족하는 공의 순서 ( 오름차순 ) 이 되기에 기존에 구한 answer ( 공의 총 갯수만 만족 ) 에 이전에 계산한 indexer 를 참조하여 값을 넣어주면 됩니다.

 

// 트리 구성을 위한 노드 정의
class node {
    constructor(idx) {
        this.idx = idx;
        this.child = [];

        this.Satisfied = false;

        this.count = 0;
        this.child_idx = 0;
    }
    flow() {
        if (this.child.length == 0) {
            this.count += 1;
            return [this.count, this];
        } else {
            var r = this.child[this.child_idx].flow();
            this.child_idx = (this.child_idx + 1) % this.child.length;

            return r;
        }
    }
    addChild(c) {
        this.child.push(c);
    }
    getLeafNodes() {
        return this.child.map(c => {
            if (c.child.length == 0) {
                return c;
            } else {
                return c.getLeafNodes();
            }
        }).flat();
    }
    sort() {
        this.child.sort((a, b) => a.idx - b.idx);
    }
}

// 트리 구조를 생성함
function makeTree(edges) {
    var map = {
        1: new node(1)
    };

    edges.forEach(edge => {
        var [p, c] = edge;
        if (!map[p]) {
            map[p] = new node(p);
        }
        if (!map[c]) {
            map[c] = new node(c);
        }

        map[p].addChild(map[c]);
    });

    for (var i in map) {
        map[i].sort();
    }

    return map[1];
}

function patternMap(pattern) {
    var map = {};

    for (var i = 0; i < pattern.length; i++) {
        var idx = pattern[i];
        var arr = map[idx] || [];
        arr.push(i);
        map[idx] = arr;
    }

    return map;
}

function solution(edges, target) {
    var root = makeTree(edges);

    function isSucc() {
        return leafs.every(leaf => leaf.Satisfied);
    }

    var leafs = root.getLeafNodes();

    leafs.forEach(leaf => {
        if (target[leaf.idx - 1] == 0) {
            leaf.Satisfied = true;
        }
    });

    var pattern = [];
    while (!isSucc()) {
        var [count, node] = root.flow();

        pattern.push(node.idx);

        if (target[node.idx - 1] < count) {
            return [-1];
        } else if (target[node.idx - 1] <= count * 3) {
            node.Satisfied = true;
        }
    }

    var map = patternMap(pattern);
    var answer = new Array(pattern.length);

    leafs.forEach(leaf => {
        var targetNum = target[leaf.idx - 1];
        var count = leaf.count;
        if (count == 0) return;

        var arr = new Array(count).fill(1);
        var sum = count;
        var lastIndex = arr.length - 1;
        while (sum != targetNum) {
            var diff = targetNum - sum;

            if (diff > 2) {
                sum += 2;
                arr[lastIndex--] = 3;
            } else {
                sum += diff;
                arr[lastIndex] += diff;
            }
        }

        var indexs = map[leaf.idx];

        for (var i = 0; i < indexs.length; i++) {
            answer[indexs[i]] = arr[i];
        }
    });

    return answer;
}