LeetCode: 59번 (Spiral Matrix II) [JAVA]

문제 링크

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

Spiral Matrix II - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 n 크기를 바탕으로 n x n 크기의 이차원 배열을 선언
2. 한 번에 이동할 크기 size, 현재 위치인 행과 열을 나타낼 변수, 이동량, 넣을 값을 선언
3. while문을 통해 열 -> 행 이동을 반복하여 배열을 나선형 형태로 채움
   1) size만큼 반복을 하여 열 이동을 하며, 해당 위치에 값을 저장
   2) size 감소
   3) size만큼 반복을 하여 행 이동을 하며, 해당 위치에 값을 저장
   4) 이동량 변경
   5) 위 과정을 size가 0보다 클때 까지 반복
4. 결과 배열 반환

 해당 문제 유형 자체가 어느정도 유명하여, 다양한 풀이가 존재하는 문제이다. 결국 나선형 형태의 움직임을 (열 이동 -> 행 이동)의 반복으로 볼 수 있다. 움직임을 보면 우선 열을 따라 +1씩 움직이며 가다가, 이후 행 이동으로 방향을 바꾸고 +1씩 움직인다. 그 다음에는 열을 따라 -1씩 움직이다가, 다시 행을 따라 -1씩 움직이는 형태가 된다. 결국 앞선 움직임이 계속 반복되는 형태가 된다.
 물론 이때 움직이는 양은 또 차이가 존재하는데, 처음 열을 이동할 때는 주어진 크기 n만큼 움직이다가, 그 다음에는 행과 열을 n-1씩 움직이고, 그 다음엔 행과 열을 n-2씩 움직이는 2번 반복되는 형태가 된다. 결국 이동 방향은 (열, 행) 쌍으로 묶을 수 있지만, 움직이는 이동량의 경우 첫 열 이동을 제외하고 (행, 열) 쌍으로 묶어줘야 한다.
 이를 반영하여 전체 while문을 통해 이동하는 로직을 작성할 때, 번갈아가며 움직이는 크기를 줄여주거나 이동량(이동방향)을 바꿔주는 로직을 사이에 끼워넣어줘야 한다. 우선 한 번에 가야할 거리 size, 현재 위치(행과 열)를 담는 변수, 이동량(시작은 +1씩), 저장할 값을 나타내는 count를 선언하고, 하나의 while문을 통해 배열을 채운다
 우선 처음은 열을 따라 size만큼 이동하며, 각 위치에 값을 저장해준다. 그 다음엔 size를 한 번 감소해주고, size만큼 행 이동을 하며 각 위치에 값을 저장해준다. 그리고 나서는 이동량에 -1을 곱해, 기존의 +1씩 움직이는 이동량을 -1로 바꿔준다. 이렇게 되면 다음 열과 행 이동을 -1씩 감소하며 움직이게 된다.
 이후에는 단순히 while문을 통해 움직이는 거리 size가 0이 될 때까지 반복을 하고, 이후 값을 채워넣은 이차원 배열 answer를 반환하면 된다.

 

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] answer = new int[n][n];
        int size = n, r = 0, c = -1, move = 1, count = 0;

        while (size > 0) {//이동거리가 0보다 큰 동안
            for (int i = 0; i < size; i++) {//이동거리만큼
                c += move;//열 이동
                answer[r][c] = ++count;//그때마다 증가된 값 저장
            }
            --size;//이동거리 감소

            for (int i = 0; i < size; i++) {//이동거리만큼
                r += move;//행 이동
                answer[r][c] = ++count;//그때마다 증가된 값 저장
            }
            move *= -1;//이동방향 변경

        }

        return answer;
    }
}

결과