Notice
Recent Posts
Recent Comments
Link
.Zzumbong
[leetCode/JS] 931. Minimum Falling Path Sum ๋ณธ๋ฌธ
๋์ด๋ [ ๐ค ] 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 |
0 Comments