알고리즘/알고리즘 문제풀이
BinaryTree,PrefixSum_Leetcode_437. Path Sum III [swift]
Downey
2025. 3. 10. 17:11
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 = 이전합 이 되는 것이다.
반성
아직도 문제를 잘 읽고 푸는 방법. 처음 계획대로 로직을 구성하는 것을 잘 하지 못하고 있다.
연습이 더 필요해 보인다.