BinaryTree,PrefixSum_Leetcode_437. Path Sum III [swift]

https://leetcode.com/problems/path-sum-iii/description/?envType=study-plan-v2&envId=top-100-liked

 

반성

문제 해석에 실수가 있었다.

왜인지 모르겠지만, Path를 이루는 element의 최대값이라고 생각해버렸다.

그런데 그냥 Path의 갯수를 return 하는 것 이었음.

접근방법

• 재귀 탐색을 수행한다.
• 재귀 이동 시, history: [Int]를 전달한다. history에는 node.val을 append하며 진행한다.
• history의 합산과 targetSum이 일치할 경우, sols: [Int]에 해당 history.count를 append한다. ( 반성에서 작성된 오류 로직이 여기서 탄생 )
• history의 합산이 targetSum을 넘어도, 계속 탐색한다. 음수 양수가 더해지며 targetSum이 될수도 있기 떄문. (그런데 코드에 반영은 이상하게 되었다)
• 자신 노드에서 수행후, 자식노드에서 반복한다.

오답코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    // history에 자기자신을 더한다. -> history array를 전달. 갯수와 element를 알 수 있다. reduce하여 종료 조건 판단.
    // over -> 자기자신으로 부터 재시작.
    // else -> 자식으로 넘어감. left 먼저
    // 적합 -> sols 에 append한다.

    // 아 문제를 잘못읽었다. 경로에 포함된 element node의 갯수가 아니라. 경로 자체의 갯수다.

    // 아래 코드의 반례, targetSum이 음수. 그러면 대소비교 로직이 성립하지 않는다.
    // 방법 1 targetSum의 부호에 따른 로직을 재구성
    // 방법 2 둘 다 커버가능한 로직의 재설립.

    var sols = [Int]()

    func pathSum(_ root: TreeNode?, _ targetSum: Int) -> Int {
        guard let root else { return 0 }

        excute(node:root, history: [], target: targetSum)
        print(sols)
        return sols.count
    }

    func excute(node: TreeNode?, history: [Int], target: Int) {
        guard let node else { return }
        var history = history
        history.append(node.val)
        let currentSum = history.reduce(0, { $0 + $1 } )
        
        if currentSum == target { // 적합. 
            sols.append(history.count)
            print(history)
        } else if currentSum < target {
            excute(node:node.left, history: history, target: target) // lhs
            excute(node:node.right, history: history, target: target) // rhs
        } else if node.val < target { 
            excute(node:node, history: [], target: target)
        }

        excute(node:node.left, history: [], target: target) 
        excute(node:node.right, history: [], target: target) 

    }

}

오답 케이스 testCase 75/129

root = [-2,null,-3] targetSum = -5

TargetSum이 음수인 경우에 대한 대응이 되지 않는다.

음수에 대한 로직을 추가하거나, 로직을 전체 재설계 해야 함.

 

오답코드 2

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    // history에 자기자신을 더한다. -> history array를 전달. 갯수와 element를 알 수 있다. reduce하여 종료 조건 판단.
    // over -> 자기자신으로 부터 재시작.
    // else -> 자식으로 넘어감. left 먼저
    // 적합 -> sols 에 append한다.

    // 아 문제를 잘못읽었다. 경로에 포함된 element node의 갯수가 아니라. 경로 자체의 갯수다.

    // 아래 코드의 반례, targetSum이 음수. 그러면 대소비교 로직이 성립하지 않는다.
    // 방법 1 targetSum의 부호에 따른 로직을 재구성
    // 방법 2 둘 다 커버가능한 로직의 재설립.

    var sols = [Int]()

    func pathSum(_ root: TreeNode?, _ targetSum: Int) -> Int {
        guard let root else { return 0 }

        excute(node:root, history: [], target: targetSum)
        print(sols)
        return sols.count
    }

    func excute(node: TreeNode?, history: [Int], target: Int) {
        guard let node else { return }
        var history = history
        history.append(node.val)
        let currentSum = history.reduce(0, { $0 + $1 } )
        print("$$$$$ \(node.val)")
        if currentSum == target { // 적합. 
            sols.append(history.count)
            // print("currentSum == target", history)
        } else if target < 0 { // 음수 targetSUm
            // print("if target < 0")
            if currentSum > target {
                excute(node:node.left, history: history, target: target) // lhs
                excute(node:node.right, history: history, target: target) // rhs
            } else if node.val > target { 
                excute(node:node, history: [], target: target)
            }
        } else { // 양수, 0 targetSum
        // print("if target > 0")
            if currentSum < target {
                excute(node:node.left, history: history, target: target) // lhs
                excute(node:node.right, history: history, target: target) // rhs
            } else if node.val < target { 
                excute(node:node, history: [], target: target)
            }
        }

        // print("default recursive")

        excute(node:node.left, history: [], target: target)
        excute(node:node.right, history: [], target: target)

    }

}

89/129에서 다시 막힘.

1-2-3-4-5로 진행되는 1직선트리에서

[1,2], [3], [3] 으로 중복되는 값 발생

사유: 1-2-3-4-5탐색 후 , 2-3-4-5 탐색, 3-4-5 탐색을 하면서 3이 두 번 추가됨.

 

내 코드를 반영하여 GPT의 수정 로직

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    var sol = 0

    func pathSum(_ root: TreeNode?, _ targetSum: Int) -> Int {
        guard let root else { return 0 }

        excute(node:root, history: [], target: targetSum)
        return sol
    }

    
    func excute(node: TreeNode?, history: [Int], target: Int) {
        guard let node else { return }
        var history = history
        history.append(node.val)

        // 모든 서브배열의 합을 검사 (기존 reduce 방식 대신 활용)
        var sum = 0
        for value in history.reversed() { // 뒤에서부터 누적 합 검사
            sum += value
            if sum == target {
                sol += 1
            }
        }

        // 자식 노드 탐색
        excute(node: node.left, history: history, target: target)
        excute(node: node.right, history: history, target: target)
    }

}

이런저런 로직이 사라졌다..

history.reversed()의 for 구문을 통하여, history에 기록된 최 하단노드부터 더하여 올라간다.

그러므로 모든 부분합을 찾을 수 있다.

중복은 발생하지 않는다...

하지만 이 로직은 성능이 안좋다

39 ms Beats 43.94%

23.17MB Beats19.70%

 

모범 코드

class Solution {
    func pathSum(_ root: TreeNode?, _ targetSum: Int) -> Int {
        var map = [Int: Int]()
        var paths = 0
        map[0] = 1 // البداية من مجموع صفر
				   // ➡ “합이 0에서 시작함”

        func dfs(_ node: TreeNode?, _ currSum: Int) {
            guard let node = node else { return }

            let currSum = currSum + node.val
            // عدد المسارات السابقة اللي بتكمل لمجموع targetSum
            // ➡ “현재 합을 저장함”
            paths += map[currSum - targetSum, default: 0]
            
            // نخزن العدد الحالي
            // ➡ “이전에 나온 합 중에서 targetSum을 완성하는 경로의 개수”
            map[currSum, default: 0] += 1

            dfs(node.left, currSum)
            dfs(node.right, currSum)

            //  نرجع نخصم لما نرجع عشان ما يأثر على الفروع الثانية
            // ➡ “다른 서브트리에 영향을 주지 않도록, 백트래킹 시 현재 합을 제거함”
            map[currSum]! -= 1
        }

        dfs(root, 0)
        return paths
    }
}

처음에는 정말 이해가 안됐다....

주요이론

1. prefix sum(누적 합)이란?

• 루트에서 현재 노드까지의 누적된 합을 저장하는 개념.

• 특정 구간 합을 빠르게 계산할 수 있음.

 

2. prefix sum을 이용해 경로 찾는 원리

• 경로의 합이 targetSum이 되는 경우를 찾으려면:

 > prefixSum(current) - prefixSum(previous) = targetSum

 

이게 왜??? 라고 처음엔 생각된다. 자 차차 이해해보자.

 

우리는 targetSum = 8 인 경우를 찾을 때,

5-3 경로일 때 8을 만족하는군 하고 찾을 수 있다.

자, 잠깐 10 - 5 - 3 경로를 생각해보자.

합이 18이고, 10을 빼면 8이 됨을 알 수 있다.

그렇다면 현재 합 - 이전 합 = targetSum이 된다.

항 이동을 하여

현재합 - targetSum = 이전합 이 되는 것이다.

 

반성

아직도 문제를 잘 읽고 푸는 방법. 처음 계획대로 로직을 구성하는 것을 잘 하지 못하고 있다.

연습이 더 필요해 보인다.