.leetcode(337. House Robber III)

문제

https://leetcode.com/problems/house-robber-iii/

문제 해설

이 문제는 부모자식 트리로 직접 연결된 경우는 안되고 한칸 뛰어서는 도둑질이 가능한 문제이다.

문제 풀기 전

1. dp문제인걸 알았다. 이전결과가 현재결과를 얻는데 필요하니 말이다.
2. 하지만 문제를 풀지는 못했다. 자바에서는 리턴을 하나라는 고정관념에 잡혀서 였다.

직접 푼 풀이

재도전하기

느낀점

1. 리턴을 여러개 하고 싶으면 배열을 만들어서 쓰면 되었다. 사실 간단한 방법인데 자바에서는 잘 안쓰는 형식이기에 다른 방법이 있겠지하다가 결국 못 풀었다.
2. 리턴에서 2개를 갖고 있어야하는데 바로 전단계와 , 전전단계의 데이터가 있어야 지금의 단계와 합할지 말지를 결정할 수 있기 때문이다.
3. 아래는 솔루션에서 영감을 얻어 쉽게 풀어쓴 나의 풀이다. 아이디어는 int[]로 전단계에서의 총합과 전전단계까지의 총합을 넘겨받는 것이다.

• 전단계는 배열의 0번에 저장했고, 전전단계는 배열의 1번에 저장했다.
• a는 전단계의 합, b는 left는 전단계이고 right는 전전단계의 합인 케이스다. c는 left는 전전단계에 right는 전단계의 합인 케이스다. d는 left,right 모두 전전단계로 하고 대신 지금 노드의 값을 더한다.
• 이를 모두 비교해서 최대값을 구하고 전단계의 값의 합을 배열로 넘겨주면서 반복한다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    public int rob(TreeNode root) {
        int[] answer = doRob(root);
        return Math.max(answer[0], answer[1]);
    }

    private int[] doRob(TreeNode root) {
        if (root == null) {
            return new int[]{0,0};
        }

        int[] left = doRob(root.left);
        int[] right = doRob(root.right);

        int a = left[0] + right[0];
        int b = left[0] + right[1];
        int c = left[1] + right[0];
        int d = root.val + left[1] + right[1];

        return new int[]{Math.max(a,Math.max(b,Math.max(c,d))), a};
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)