.Zzumbong

[leetCode/JS] 931. Minimum Falling Path Sum ๋ณธ๋ฌธ

coding test/leetCode

[leetCode/JS] 931. Minimum Falling Path Sum

์ญ˜๋ด‰ 2022. 12. 13. 11:50

๋‚œ์ด๋„ [ ๐Ÿค” ] Medium

๋ฌธ์ œ ์„ค๋ช…

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

n x n ์ •์ˆ˜ ๋ฐฐ์—ด์ด ์ฃผ์–ด์ง„๋‹ค.
์ด ๋ฐฐ์—ด์˜ "falling path"์ค‘ ๊ฐ€์žฅ ์ž‘์€ ํ•ฉ๊ณ„์˜ ์ˆซ์ž๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋ฉด ๋œ๋‹ค.
falling path๋Š” (row, col) ์—์„œ (row+1, col-1), (row+1, col), (row+1, col+1)์˜ 3๊ฐ€์ง€ ๊ฒฝ๋กœ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค. 

 

์ž…์ถœ๋ ฅ ์˜ˆ

Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.

 

 

Example 2:

Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.

 

 

Constraints

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 100
  • -100 <= matrix[i][j] <= 100

 


 

๋‚ด ์†”๋ฃจ์…˜

  • falling path ๋ผ๋Š” ๊ฐœ๋…์„ ์ฒ˜์Œ์— ์•ˆ์ฝ๊ณ  ์ง€๋‚˜๊ฐ€์„œ ์ž ๊น ์ •์‹  ๋†“๊ณ  ๋”ด๊ฑฐ ๋งŒ๋“ค๊ณ  ์žˆ์—ˆ๋‹ค. ๐Ÿ˜‚
  • ๊ฒฝ๋กœ ์ž์ฒด๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๊ณ  ํ•ฉ๊ณ„๋ฅผ ๊ตฌํ•œ๋‹ค๋Š” ์ ์ด ์ค‘์š”.
  • ์„ค๋ช…์— ์žˆ๋Š” ๋‚™ํ•˜ ๊ฐœ๋…์œผ๋กœ ์ ‘๊ทผํ•จ.
2 1 3 โž” 2 1 3 โž” 2 1 3
6 5 4 7 6 5 7 6 5
7 8 9 7 8 9 13 13 14
  • row = 1 ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ [row-1]์— ์žˆ๋Š” [col-1], [col], [col+1] ์ค‘ ๊ฐ€์žฅ ์ž‘์€ ์ˆซ์ž์™€ ํ•ฉ์นœ๋‹ค.
  • [row][-1] ์ด๋‚˜ [row][col.length < n]๊ฐ€ ๋˜์–ด undefined ์ผ ์ˆ˜ ๋„์žˆ์œผ๋‹ˆ ์ฒดํฌํ•œ๋‹ค.
  • matrix์˜ ๋งˆ์ง€๋ง‰ row์ค‘ ๊ฐ€์žฅ ์ž‘์€ ์ˆซ์ž๋ฅผ returnํ•˜๋ฉด ๋‹ต์ด ๋œ๋‹ค.
var minFallingPathSum = function(matrix) {
  const check = (n) =>  n !== undefined ? n : Infinity;
  for(let row = 1; row < matrix.length; row++) {
    for(let col = 0; col < matrix[0].length; col++) {
      matrix[row][col] = matrix[row][col] + 
      	Math.min(
          check(matrix[row-1][col-1]),
          check(matrix[row-1][col]),
          check(matrix[row-1][col+1])
        );
    }
  }
  return Math.min(...matrix[matrix.length-1]);
};

์ฒ˜์Œ์— ์ง  ๋ณด๊ธฐ ์ข‹์€ ์ฝ”๋“œ. ์†๋„ 103ms, ๋ฉ”๋ชจ๋ฆฌ 42.7MB.

 

 

 

var minFallingPathSum = function(matrix) {
  for(let row = 1; row < matrix.length; row++) {
    for(let col = 0; col < matrix[0].length; col++) {
      matrix[row][col] = matrix[row][col] + Math.min(
        matrix[row-1][col-1] !== undefined ? matrix[row-1][col-1] : Infinity,
        matrix[row-1][col] !== undefined ? matrix[row-1][col] : Infinity,
        matrix[row-1][col+1] !== undefined ? matrix[row-1][col+1] : Infinity,
      );
    }
  }
  return Math.min(...matrix[matrix.length-1]);
};

๋ณด๊ธฐ์—” ํ™”๋‚จ. ์†๋„ 89ms, ๋ฉ”๋ชจ๋ฆฌ 43.5 MB

 

๊ฐ์ƒํ‰

  • ์ฒ˜์Œ์—” DFS๋ฅผ ์ด์šฉํ•˜๋ ค๋‹ค๊ฐ€ ๋ณต์žกํ•ด์ ธ์„œ ์ •์‹  ๋†”๋ฒ„๋ฆผ.ใ…‹ใ…‹
  • ๊ทธํ›„์—” row๋ฅผ ์—ญ์ˆœ์œผ๋กœ ์˜ฌ๋ผ๊ฐ€๋Š” ์ฝ”๋“œ๋กœ ์งฐ๋‹ค๊ฐ€. ๋‚ด๋ ค๊ฐ€๋„ ๋œ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์–ด์„œ ๋‹ค์‹œ row++๋กœ ์งฌ.
  • ๋ถ„๋ช… ๋ฏธ๋””์—„์ด์˜€๋Š”๋ฐ..  ๋งŽ์ด ํ’€์–ด๋ด์•ผ ์‰ฌ์šด ๋ฌธ์ œ๋“ค์ด ๋งŽ๋‹ค.

'coding test > leetCode' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[leetCode/JS] 152. Maximum Product Subarray  (0) 2022.12.14
[leetCode/JS] 198. House Robber  (0) 2022.12.14
[leetCode/JS] 70. Climbing Stairs  (0) 2022.12.12
[leetCode/JS] 124. Binary Tree Maximum Path Sum  (0) 2022.12.11
[leetCode/JS] 1339. Maximum Product of Splitted Binary Tree  (0) 2022.12.10
Comments