.leetcode(437. Path Sum III)

문제

https://leetcode.com/problems/path-sum-iii/

문제 풀기 전

1. 배열이 앞,뒤 접근을 고민했다면 트리는 위아래 출발을 고민한다.
2. 위에서 출발하면 넘겨주는 파라미터를 배열로 해서 합한값, 본인을 내려주면 될거같다.
3. 위에서 접근하는 방식을 취해보자

직접 푼 풀이

소요시간: 14분(09:31 ~ 09:45)

class Solution {
    private int count=0;
    public int pathSum(TreeNode root, int sum) {
        pathSum(root, sum, new ArrayList());
        return count;
    }

    private void pathSum(TreeNode root, int sum, List<Integer> list) {
        if (root == null) {
            return;
        }

        List<Integer> newList = new ArrayList<>();
        for (int i=0; i<list.size(); i++) {
            int val = list.get(i) + root.val;
            if (val == sum) {
                count++;
            }
            newList.add(i, val);
        }
        newList.add(root.val);
        if (root.val == sum) {
            count++;
        }

        pathSum(root.left, sum, newList);
        pathSum(root.right, sum, newList);
    }
}

느낀점

1. 내가 푼 풀이는 사실 공간이 거의 O(n^2)으로 필요할 것으로 보인다. 효율적인 공간활용 풀이는 아니다.
2. 이런 합 문제는 되도록 합을 파라미터로 옮기는게 좋은거 같다. 그리고 그 합에 갯수를 구하는 문제면 합별 개수를 카운트 한걸 저장해보도록 하자.
3. 트리에서 어떻게 결과를 저장할건지를 물어보는것으로 보인다.
4. 공간을 O(n)으로 만들기 위해서는 기가막힌 생각의 전환이 필요하다. 즉 모든 합에서 내가 구하고자 하는 주어진 sum을 뺀 기록이 있었는지를 보면 되는것이다.

• 제일 왼쪽 노드를 가정하고 1,2,3,4 로 가정하고 7이라는 sum을 구한다고 했을때, 모든 숫자를 더해가며 저장한다고 생각해보자.
• 1번 왔을 때 1 저장
• 2번 왔을 때 1,3 저장 <- 3은 1+2한 값이다.
• 3번 왔을 때 1,3,6 저장 <- 6은 1+2+3한 값이다.
• 4번 왔을 때 1,3,6,10 저장 <- 10은 1+2+3+4한 값이다.
  • 여기 합에서 구하고자하는 sum인 7을 뺐을때 3이라는 숫자가 나오는데 우리가 저장한 숫자 3이 있으므로 카운트 할 수 있다.
  • 이 말은 3까지 저장한 노드 이후로 노드를 모두 더하면 우리가 구하고자하는 값이 나온다는 말이다.
• 이 아이디어를 구현은 아래와 같다.

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

class Solution {
    private int count=0;
    private int targetSum=0;
    private Map<Integer, Integer> map = new HashMap<>();
    public int pathSum(TreeNode root, int sum) {
        targetSum = sum;
        solve(root, 0);
        return count;
    }

    private void solve(TreeNode root, int currentSum) {
        if (root == null) {
            return;
        }

        currentSum += root.val; 
        if (currentSum == targetSum) {
            count++;
        }

        count += map.getOrDefault(currentSum - targetSum, 0);

        map.put(currentSum, map.getOrDefault(currentSum, 0)+1);       

        solve(root.left, currentSum);
        solve(root.right, currentSum);

        map.put(currentSum, map.get(currentSum) - 1);
    }
}

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

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