(Leetcode) 54 - Spiral Matrix 풀이
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/spiral-matrix/description/
내가 작성한 풀이
복잡한 부분은 없다. 문제에서 설명된 spiral 순회 방식을 그대로 코드로 옮기면 된다.
class Solution {
final int VISITED = 101;
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ordered = new ArrayList<>();
int i = 0;
int j = 0;
int depth = 0; // 한 바퀴 돌 때 마다 안쪽으로 들어가게 됨.
int startI = Integer.MIN_VALUE;
int startJ = Integer.MIN_VALUE;
while (!(i == startI && j == startJ)) {
startI = i;
startJ = j;
// 마지막에서 i++ 을 진행하는데 이로 인해서 범위를 초과하는 것을 방지
if (i == matrix.length) {
break;
}
// 오른쪽으로 이동
while (j < matrix[0].length - depth) {
update(matrix, i, j, ordered);
j++;
}
j--;
// 아래로 이동
while (i < matrix.length - depth) {
update(matrix, i, j, ordered);
i++;
}
i--;
// 왼쪽으로 이동
while (j > depth - 1) {
update(matrix, i, j, ordered);
j--;
}
j++;
// 위로 이동
while (i > depth - 1) {
update(matrix, i, j, ordered);
i--;
}
i++;
// while 조건에 걸리지 않도록 다음 칸으로 이동
i++;
j++;
depth++;
}
return ordered;
}
private void update(int[][] matrix, int i, int j, List<Integer> ordered) {
if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) {
return;
}
if (matrix[i][j] != VISITED) {
ordered.add(matrix[i][j]);
}
matrix[i][j] = VISITED;
}
}
TC, SC
문제에서 다음과 같이 정의 되어 있다.
m == matrix.length
n == matrix[i].length
시간복잡도는 O(m * n), 공간복잡도는 O(1) 이다. (공간복잡도의 경우 결과를 위해 생성되는 List는 계산에서 제외함.)