프로필사진

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;
}
}
반응형
댓글
반응형
인기글
Total
Today
Yesterday
«   2025/03   »
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
글 보관함