Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 메탈퍼즐
- 노노그램
- 게임
- 코딩테스트
- LeetCode
- 코테
- 취미
- 알고리즘테스트
- 토이프로젝트
- 밥먹고
- 하스스톤
- 맛집
- 서울제빵소
- DIY
- 발더스게이트
- 잠실새내
- 메일우유
- 나쫌
- 바질토마토뭐시기
- 발더스모드
- 뜨아거
- 버즈2프로
- 눈알빠지겠네
- 송리단
- 3d퍼즐
- 천등
- 발더스3
- 미앤아이
- javascript
- 누룽지소금빵
Archives
- Today
- Total
.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 |
Comments