Algorithm - Programmers & LeetCode Problems 5

Programmers Problem lev.3 정수 삼각형

• 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

• 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

예시

• 입출력 예
  • 입력값 : [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
  • 출력값 : 30

Solution

• 시간 초과된 풀이 (재귀)

function solution(triangle) {
    let answer = 0;
    
    const dp = (rowIndex, colIndex, sum) => {
        if (rowIndex >= triangle.length) {
            answer = Math.max(answer, sum);
            return;
        }
        sum += triangle[rowIndex][colIndex];
        dp(rowIndex + 1, colIndex, sum);
        dp(rowIndex + 1, colIndex + 1, sum);
    };
    
    dp(0, 0, 0);
    return answer;
}

• 다른 사람 코드를 참고한 풀이 (DP)

function solution(triangle) {
    const dp = triangle.slice();
    
    for (let i = dp.length - 2; i >= 0; i--) {
        for (let j = 0; j < dp[i].length; j++) {
            dp[i][j] += Math.max(dp[i + 1][j] || 0, dp[i + 1][j + 1] || 0);
        }
    }
    
    return dp[0][0];
}

Programmers Problem lev.3 등굣길

• 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

• 아래 그림은 m = 4, n = 3 인 경우입니다.

• 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

• 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

• 입력값 : m = 4, n = 3, puddles = [[2, 2]]
• 출력값 : 4

Solution

function solution(m, n, puddles) {
    let answer = 0;
    const MOD =  1000000007;
    const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
    
    puddles.forEach(([x, y]) => {
        dp[y][x] = -1;
    });
    
    dp[1][1] = 1;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (i === 1 && j === 1) {
                continue;
            }
            if (dp[i][j] === -1) {
                dp[i][j] = 0;
                continue;
            }
            
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
        }
    }
     
    return dp[n][m];
}

LeetCode Problem 513. Find Bottom Left Tree Value

• Given the root of a binary tree, return the leftmost value in the last row of the tree.

Examples

• Example 1
  • Input: root = [2,1,3]
  • Output: 1

• Example 2
  • Input: root = [1,2,3,4,null,5,6,null,null,7]
  • Output: 7

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• -2^31 <= Node.val <= 2^31 - 1

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
    const queue = [root];
    let level = [];

    while  (queue.length) {
        let size = queue.length;
        level = [];

        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            level.push(node.val);

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }

    return level[0];
};