1339. Maximum Product of Splitted Binary Tree

주어진 이진트리에서 하나의 엣지 를 잘라서 각각의 서브 트리를 만들 때 두 서브 트리 합의 곱이 가장 큰 값을 리턴하는 문제이다.

10**4 까지 노드 가 주어진다고 가정한다면 9999개 의 엣지가 생길 수 있고 완탐 때려도 충분히 가능하다고 생각해 규칙을 찾기 시작했다. 

주어지는 트리가 이진트리 라고 가정한다면 최초 만나는 이중 노드에서 각각의 서브 트리 연산을 진행해 최소 최대 값을 구해 곱해주면 된다고 생각했다.

첫 번째 코드를 보자.

class Solution {
    int total = 0;
    int module = (int) Math.pow(10,9)+7;
    public int maxProduct(TreeNode root) {
        if(root == null) return 0;
        TreeNode hasSubNodes = getTotalBeforeSplit(root);
        
        int subTotalLeft = getSubTotal(hasSubNodes.left);
        int subTotalRight = getSubTotal(hasSubNodes.right);
        total += Math.min(subTotalLeft, subTotalRight);
        return (total * Math.max(subTotalLeft,subTotalRight))%module;
    }
    public int getSubTotal(TreeNode node){
        int subTotal = 0;
        if(node == null) return subTotal;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(node);
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            subTotal += cur.val;
            if(cur.left != null) q.offer(cur.left);
            if(cur.right != null) q.offer(cur.right);
        }
        return subTotal%module;
    }

    public TreeNode getTotalBeforeSplit(TreeNode root){
        total = (total+root.val)%module;
        if(root.left != null && root.right == null){
            return getTotalBeforeSplit(root.left);
        }
        if(root.right != null && root.left == null)
            return getTotalBeforeSplit(root.right);
        return root;
    }
}

getTotalBefoeSplit을 이용해 최초 만나는 이중 노드까지 의 합과 현재 노드의 위치를 기록했다. 

getSubTotal을 이용해 좌우 값을 모두 연산해 주었다. 

테스트 코드는 잘통과 된다. 바로 제출했다. 실패 ㅠㅠ

내 로직의 문제점 이 발생했다. 편향 트리인경우 내 로직이 작동하지 않는다... 노드를 끝까지 탐색해 결국 0이라는 답이 나온다. 

if를 넣어 편향 트리인 경우를 핸들링하려고 했으나 깊이를 알 수 없기 때문에 불가능하다는 결론에 도달.

 

만약 배열에서 내가 이걸 계산한다면 어떻게 할까 고민 하다 보니 prefix를 이용한 배열을 이용해 구한다는 생각에 도달했다.

 1. 모든 노드 의 합을 구한다.

2. 모든 노드 의 합을 구하는 히스토리를 입력해 prefix를 작성한다.

3. prefix 기준으로 각 서브트리의 합은 prefix , 모든 노드의 합 - prefix이다.

 

로직 이 보다 명확해졌다.

 

사실 long 타입을 쓰기 싫어서 모듈을 각각 연산마다 해주려고 했더니 prefix 본질에 어긋나 버린다. 만약 1e9 + 7의 값이 넘어가 버린다면 모듈 된 값이 prefix에 기입되어 명확한 토털 값 계산이 되질 않는다. 

 

이렇게 두개의 값을 이용해 차이 값을 구할때 prefix 합을 염두해 두고 풀이법 을 생각해보는것도 좋은것 같다.