Leetcode
[Leetcode] 54. Spiral Matrix - JS
Wix
2024. 10. 10. 10:00
1. 문제 분석
문제분석
--------------------
- m x n 행렬이 주어질 때, 나선 순서로 반환하라.
제한조건
--------------------
- m === matrix.length
- n == matrix[i].length
- 1 <= m, n <= 10
- -100 <= matrix[i][j] <= 100
2. 접근 방법
접근방법
--------------------
left, right, top, bottom 포지션을 미리 지정해두고 각 지점별로 조건을 걸어 나선 순서를 만들어준다.
예를 들어, 첫번째로 좌->우 방향으로 순서를 추가한 뒤 top++
두번째로 상->하 방향으로 순서를 추가한 뒤 right--
세번째로 우->좌 방향으로 순서를 추가한 뒤 bottom--
네번째로 하->상 방향으로 순서를 추가한 뒤 left++
3. 코드
var spiralOrder = function(matrix) {
let top = 0;
let left = 0;
let right = matrix[0].length - 1;
let bottom = matrix.length - 1;
const res = [];
while (left <= right && top <= bottom) {
for (let i = left; i <= right; i++) {
res.push(matrix[top][i]);
}
top++;
for (let i = top; i <= bottom; i++) {
res.push(matrix[i][right]);
}
right--;
if (top <= bottom) {
for (let i = right; i >= left; i--) {
res.push(matrix[bottom][i])
}
bottom--;
}
if (left <= right) {
for (let i = bottom; i >= top; i--) {
res.push(matrix[i][left]);
}
left++;
}
}
return res;
};
4. 복잡도 분석
- 시간복잡도: O(n * m)
- 공간복잡도: O(n * m)
각 조건에 따라 top, left, right, bottom 위치까지 반복하여 순서를 추가한 뒤, 해당 포지션을 변경하였다.
위와 관련된 문제를 예전에 풀어본 적이 있는데 알듯 말듯 하면서 헷갈렸다.
여러번 풀어봐야겠다...