Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://leetcode.com/problems/spiral-matrix/
Spiral Matrix - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
풀이
난이도: Medium
재귀 형식으로 해결한 문제.
행렬을 나선형 순서로 돌아가기 위해서는 결국에는 외각을 한 바퀴 돌고 한 칸 안쪽에서 다시 한 바퀴 도는 것을 반복하게 된다.
따라서 재귀로 표현하기 적합하다.

한 칸의 외각의 범위를 표현하기 위해서는 단 두가지 점인, 왼쪽 위(left top)와 오른쪽 아래(right bottom)만 알면 된다.

이제 왼쪽 위(left top)와 오른쪽 아래(right bottom)점을 기준으로 외각을 한 바퀴 순회한 순서를 구하는 함수 호출하여 leftTop과 rightBottom을 대각선으로 좁혀주면 모든 칸을 순회할 수 있다.
leftTop의 row가 rightBottom 보다 큰 게 역전된 경우와 leftTop의 column이 rightBottom 보다 크게 역전된 경우 모든 칸을 순회한 것이므로 종료해주면 된다.

코드
class Pair{ | |
int r, c; | |
Pair(int r, int c){ | |
this.r = r; | |
this.c = c; | |
} | |
} | |
class Solution { | |
public List<Integer> getOutsideSpiralOrder(Pair leftTop, Pair rightBottom, int[][] matrix){ | |
List<Integer> order = new ArrayList<>(); | |
for(int c = leftTop.c; c< rightBottom.c ; ++c) | |
order.add(matrix[leftTop.r][c]); | |
for(int r = leftTop.r; r<= rightBottom.r ; ++r ) | |
order.add(matrix[r][rightBottom.c]); | |
if(leftTop.r == rightBottom.r || leftTop.c == rightBottom.c) | |
return order; | |
for(int c = rightBottom.c -1; leftTop.c < c ; --c) | |
order.add(matrix[rightBottom.r][c]); | |
for(int r = rightBottom.r; leftTop.r < r ; --r) | |
order.add(matrix[r][leftTop.c]); | |
return order; | |
} | |
public List<Integer> spiralOrder(int[][] matrix) { | |
int row = matrix.length; | |
int column = matrix[0].length; | |
List<Integer> linkedOrders = new ArrayList<>(); | |
Pair leftTop = new Pair(0,0); | |
Pair rightBottom = new Pair(row -1, column -1); | |
while(leftTop.r <= rightBottom.r && leftTop.c <= rightBottom.c){ | |
linkedOrders.addAll(getOutsideSpiralOrder(leftTop,rightBottom,matrix)); | |
leftTop.r++; leftTop.c++; | |
rightBottom.r --; rightBottom.c--; | |
} | |
return linkedOrders; | |
} | |
} |
'알고리즘 공부 > LeetCode' 카테고리의 다른 글
[LeetCode] 79. Word Search (C++, DFS) (0) | 2022.08.31 |
---|---|
[LeetCode] 48. Rotate Image (C++, in-place) (0) | 2022.08.22 |
[LeetCode] 73. Set Matrix Zeroes (Java, In-place) (0) | 2021.12.08 |
[LeetCode] 23. Merge k Sorted Lists (Java, C++) (0) | 2021.12.06 |
[LeetCode] 21. Merge Two Sorted Lists (Java) (0) | 2021.12.05 |