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++로 짬.
- 분명 미디엄이였는데.. 많이 풀어봐야 쉬운 문제들이 많다.