Post

[LeetCode] #54 - Spiral Matrix [Java][C++][Python]

[LeetCode] #54 - Spiral Matrix [Java][C++][Python]

문제 링크


1. 아이디어

$m \times n$ 행렬의 원소를 바깥 테두리에서 안쪽으로 나선 순서로 모으는 문제로, 위쪽 행, 오른쪽 열, 아래쪽 행, 왼쪽 열을 차례로 훑고 훑은 줄만큼 그 쪽 경계를 한 칸 안으로 좁히는 것을 한 바퀴로 반복하면 모든 칸이 정확히 한 번씩 담긴다. 다만 위쪽 행과 오른쪽 열을 훑고 경계를 좁힌 뒤 남은 영역이 비면, 좁히기 전 영역이 한 행이나 한 열뿐이라 그 두 단계에서 이미 다 담긴 것이므로, 반복을 여기서 끝내야 아래쪽 행과 왼쪽 열이 같은 칸을 반대 방향으로 다시 담지 않는다. 한 바퀴를 마친 뒤에는 다음 바퀴의 반복 조건이 같은 검사를 하므로 따로 확인하지 않아도 된다.


2. 코드

풀이 [Java][C++][Python]

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
31
32
33
34
35
import java.util.*;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) {
                ans.add(matrix[top][c]);
            }
            top++;

            for (int r = top; r <= bottom; r++) {
                ans.add(matrix[r][right]);
            }
            right--;

            if (top > bottom || left > right) break;

            for (int c = right; c >= left; c--) {
                ans.add(matrix[bottom][c]);
            }
            bottom--;

            for (int r = bottom; r >= top; r--) {
                ans.add(matrix[r][left]);
            }
            left++;
        }

        return ans;
    }
}
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
#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int top = 0, bottom = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;

        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) ans.push_back(matrix[top][c]);
            top++;

            for (int r = top; r <= bottom; r++) ans.push_back(matrix[r][right]);
            right--;

            if (top > bottom || left > right) break;

            for (int c = right; c >= left; c--) ans.push_back(matrix[bottom][c]);
            bottom--;

            for (int r = bottom; r >= top; r--) ans.push_back(matrix[r][left]);
            left++;
        }

        return ans;
    }
};
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
class Solution:
    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
        ans = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1

        while top <= bottom and left <= right:
            for c in range(left, right + 1):
                ans.append(matrix[top][c])
            top += 1

            for r in range(top, bottom + 1):
                ans.append(matrix[r][right])
            right -= 1

            if top > bottom or left > right:
                break

            for c in range(right, left - 1, -1):
                ans.append(matrix[bottom][c])
            bottom -= 1

            for r in range(bottom, top - 1, -1):
                ans.append(matrix[r][left])
            left += 1

        return ans

This post is licensed under CC BY 4.0 by the author.