Daily LeetCode Challenge - 112. Path Sum

안드로이드 개발을 하면서, 생각보다 자료구조와 복잡한 로직을 짤 일이 많아서 꾸준히 알고리즘 공부를 하고 있었다.

오늘부터 LeetCode 일일챌린지를 기록해보고자 한다. 나중에 시간이 남는다면 프로그래머스에서 푼 문제들도 조금씩 블로그에 기록해봐야겠다.

Problem From.
https://leetcode.com/problems/path-sum/

오늘 문제는 트리에서 root 부터 leat 까지의 모든 수를 더했을 때 targetSum 과 같아지면 true 를 반환하는 간단한 문제였다. DFS 와 완전탐색 둘다 필요하다고 생각한다.

트리안에서 root 부터 leaf 까지 모든 수를 다 더해보면서, targetSum 과 같아져서 true 값이 나오면 그 값을 보존해둬야 했는데, 그렇게 하기 위해서 BooleanArray 를 활용했다.

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
    
        root ?: return false
        
        val answer = BooleanArray(1)
        answer[0] = false
        
        pathSum(root, targetSum, 0, answer)
        
        return answer[0]
    }
    
    private fun pathSum(root : TreeNode, targetSum : Int, prevSum : Int, answer : BooleanArray) : BooleanArray {
        var sum = prevSum + root.`val`
        if(sum == targetSum && root.left == null && root.right == null) answer[0] = true
        
        root.left?.let {
            pathSum(it, targetSum, sum, answer)
        }
        
        root.right?.let {
            pathSum(it, targetSum, sum, answer)
        }
        
        return answer
    }
}

다 풀고나서 다른 사람들의 solution 을 보다가 더 깔끔한 방법을 찾아서 공유하고자 한다.

class Solution {
    
    fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
        if (root == null) return false
        
        val newTarget = targetSum - root.`val`
        
        if (root.left == null && root.right == null) return newTarget == 0
        
        return hasPathSum(root?.left, newTarget) || hasPathSum(root?.right, newTarget)
    }
}

위 풀이는 눈여겨볼게 두가지 있는데,
하나는 targetSum 부터 값을 빼나가면서 0이 되면 true 를 반환하도록 만든것과
다른 하나는 내 풀이처럼 answer 를 저장할 공간을 만들지 않고, 결과값을 반환하도록 만든 것이다.
위와 같이 풀이하면 결과값을 저장해두느라 메모리를 소모할 일이 없어서 조금 더 효율적일 것 같다.

알고리즘은 내가 스스로 푸는것도 재미있지만, 다 풀고나서 내 생각과 다른 사람의 생각을 비교하면서 더 좋은 방법을 배워나가는 그 과정이 정말 유익하고 좋은것 같다.