[LeetCode] 54. Spiral Matrix (Java)

문제

 

https://leetcode.com/problems/spiral-matrix/

Spiral Matrix - LeetCode

 

풀이

 

난이도: 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;
	}
	}

view raw Spiral Matrix.java hosted with ❤ by GitHub