[JAVA] LeetCode - Spiral Matrix II - 59

문제내용

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

Spiral Matrix II - LeetCode

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

 

Example 1:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

Constraints:

• 1 <= n <= 20

---

문제 접근 방법

이번 문제는 nomal 난이도지만 60%이상이 푼 문제인만큼 쉬운 문제라고 생각한다.

문제는 n*n 배열을 만들고 (0,0) 부터 시작해서 나선형으로 숫자를 하나씩 채워가는 문제이다.

 

이 문제를 보고 바로 떠오른 생각은 다음과 같은 방식이다.

1. 방향을 나타내주는 변수 d와 채울 숫자가 몇인지를 나타내 주는 변수 s활용
2. d가 정의됐다면 한쪽 방향으로 쭉~ 숫자 채우기
3. 방향이 꺾이는 지점은 다음값이 배열바깥으로 나가거나 다음 요소값이 0이 아닌 수일때 방향꺾기
4. 2번과 3번을 반복하다가 최종적으로 배열의 크기와 s가 같아지면 종료.

이러한 과정을 거치면 문제를 풀수 있다. 참고로 나는 bfs를 활용해 풀었는데 다른 분의 풀이를 보면 정말 간단하게 푸신 분도 있다. 코드를 보자.

 

---

풀이

import java.util.LinkedList;
import java.util.Queue;

public class A059_Spiral_Matrix_II_Answer {
	static int[][] answer;
	public static int[][] generateMatrix(int n) {
		answer = new int[n][n];//답
		int size = n*n;//배열크기
		int d=0, s=1;//방향, 시작숫자
		int x=0, y=0;//인덱스
		
		//1일때는 bfs에서 continue때문에 반환값이 없게됨.
		if(n==1) {
			answer[0][0]=1;
			return answer;
		}
		
		//한줄씩 숫자를 반복해서 채워감.
		while(true) {
			int[] res = spiral(n,s,x,y,d);
			if(size==res[0]) break;//시작숫자가 배열크기랑 같아지면 멈춤.
			if(d==0) d=1;//오른쪽 -> 아래
			else if(d==1) d=2;//아래 -> 왼쪽
			else if(d==2) d=3;//왼쪽 -> 위
			else d=0;//위 -> 오른쪽
			//다음 값 갱신
			x = res[1];
			y = res[2];
			s = res[0];
		}
		return answer;
    }
	
	//한줄 채우기.
	public static int[] spiral(int n, int s, int x, int y, int d) {
		int[] res = new int[3];//0:채워진숫자 , 1:x인덱스, 2:y인덱스
		int[] dx = {0,1,0,-1};//하상
		int[] dy = {1,0,-1,0};//우좌
		Queue<SpiralMatrix2> q = new LinkedList<SpiralMatrix2>();

		//시작값 추가
		q.add(new SpiralMatrix2(x, y));
		answer[x][y]=s;
		
		while(!q.isEmpty()) {
			SpiralMatrix2 cur = q.poll();
			int nx = cur.x + dx[d];
			int ny = cur.y + dy[d];
			
			//다음 인덱스가 배열 바깥으로 나가거나 요소값이 0이 아니면 무시하고 다음꺼 ㄱㄱ
			if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
			if(answer[nx][ny]!=0) continue;
			
			s++;
			res[0]=s;
			res[1]=nx;
			res[2]=ny;
			q.add(new SpiralMatrix2(nx, ny));//다음 인덱스넣기
			answer[nx][ny]=s;//숫자 채우기
		}
		return res;
	}
}

class SpiralMatrix2{
	int x;
	int y;
	public SpiralMatrix2(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

더 빠르고 쉬운코드

public class A059_Spiral_Matrix_II_Solution1 {
	public static int[][] generateMatrix(int n) {
		int[][] answer = new int[n][n];
		int left = 0, top = 0;
		int right = n-1, down = n-1;
		int cnt=1;
		
		//윗줄, 오른쪽줄, 아랫줄, 오른쪽줄 순서로 숫자를 채움.
		while(left<=right) {
			for(int i=left; i<=right; i++) {
				answer[top][i] =cnt;
				cnt++;
			}
			top++;
			
			for(int j=top; j<=down; j++) {
				answer[j][right] = cnt;
				cnt++;
			}
			right--;
			
			for(int i=right; i>=left; i--) {
				answer[down][i] = cnt;
				cnt++;
			}
			down--;
			
			for(int j=down; j>=top; j--) {
				answer[j][left] = cnt;
				cnt++;
			}
			left++;
		}
		
		return answer;
	}
}

---

마치며

다른 분이 푼 로직이 훨씬 간단하고 좋은 로직으로 보인다.

문제를 어렵게 풀지 말고 쉽게풀려는 연습이 필요할듯하다.

(근데 생각해보니깐 이문제 코테에서 응용해서 나왔던 기억있다.)