LeetCode 59(Spiral Matrix II, Python)

1. 문제 링크

• Spiral Matrix II - LeetCode

Spiral Matrix II - LeetCode

 

2. 문제 설명

• n이 주어지면 n × n 행렬을 만드는데 1부터 n²까지 수를 왼쪽 상단에서 시작해서 회오리 나선 모양으로 넣기
• 54번 문제를 반대 방향으로 푸는 것이다.
• 예시) n = 3이 주어지면 [[1,2,3],[8,9,4],[7,6,5]]을 반환

3. 처음 풀이

• 54번 spiral matrix 1 문제와 비슷하게 풀었다.
• 우선 빈 매트릭스를 만든다.
• 그 다음 val=1 부터 채우면서 1씩 증가시킨다.
• x, y는 행렬의 행, 열의 인덱스이고
• delta_x, delta_y는 +-1의 값을 가져서 오른쪽, 왼쪽 또는 위쪽, 아래쪽 이동을 나타낸다.
• 그리고 up, down, left, right는 경계를 나타내는 인덱스이다.
• delta_x=1이고 x=right이면 오른쪽으로 이동하다가 오른쪽 경계를 만났다는 뜻이므로 이동 방향을 아래쪽으로 바꾸어야 한다.(delta_x=0, delta_y=1) 그리고 오른쪽 경계를 -1하여 왼쪽으로 한 칸 이동.
• 마찬가지로 delta_y=1이고 y=down이면 아래로 이동하다가 아래 경계를 만났다는 뜻이므로 이동 방향을 왼쪽으로 바꾸어야 한다.(delta_x=-1, delta_y=0) 그리고 아래쪽 경계를 +1하여 위로 한 칸 이동.
• 왼쪽 위쪽 경계도 마찬가지로 해주면 된다.

from typing import List

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # n x n 크기의 행렬을 생성하고 빈 문자열로 초기화
        matrix = [['' for _ in range(n)] for _ in range(n)]

        # 초기화할 변수들
        left = 0
        right = n - 1
        up = 1
        down = n - 1
        x, y = 0, 0
        delta_x, delta_y = 1, 0
        val = 1

        # 행렬에 값을 넣어가며 반복
        for _ in range(n**2):
            matrix[y][x] = val
            val += 1

            # 방향을 바꾸는 조건문
            if delta_x == 1 and x == right:
                delta_x, delta_y = 0, 1
                right -= 1
            elif delta_y == 1 and y == down:
                delta_x, delta_y = -1, 0
                down -= 1
            elif delta_x == -1 and x == left:
                delta_x, delta_y = 0, -1
                left += 1
            elif delta_y == -1 and y == up:
                delta_x, delta_y = 1, 0
                up += 1
            
            x += delta_x
            y += delta_y

        # 완성된 행렬 반환
        return matrix

4. 다른 풀이

• 나의 풀이와 큰 차이 없지만 그냥 한 줄씩 반복문. 

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat=[[0 for i in range(n)] for j in range(n)]
        val=1

        left,right=0,n-1
        top,bottom=0,n-1
        while  left<=right:


            #left to right
            for i in range(left,right+1):
                mat[top][i]=val
                val+=1
            top+=1

            #top to bootom
            for i in range(top,bottom+1):
                mat[i][right]=val
                val+=1
            right-=1

            #right to left
            for i in range(right,left-1,-1):
                mat[bottom][i]=val
                val+=1
            bottom-=1
            #bottom to top
            for i in range(bottom,top-1,-1):
                mat[i][left]=val
                val+=1
            left+=1

        # print(mat)
        return mat

---

• 와 이 풀이 대단하다...
• 끝에 도달하면 시계방향 90도 돌게 된다.
• (x, y)를 시계 방향 90도 회전 변환하면 (y, -x)가 되므로 이동 방향이 di, dj일 때 끝에 도달하면 그 다음 이동 방향은 dj, -di가 된다.
• 처음에 모든 값이 0인 행렬을 만들고 [1,2,3,4]를 채운 후 다시 1을 보면 0이 아니므로 끝에 도달했다는 것을 알 수 있다.

def generateMatrix(self, n):
    A = [[0] * n for _ in range(n)]
    i, j, di, dj = 0, 0, 0, 1
    for k in xrange(n*n):
        A[i][j] = k + 1
        if A[(i+di)%n][(j+dj)%n]:
            di, dj = dj, -di
        i += di
        j += dj
    return A

---

• 큰 값을 안쪽부터 채운다. 이미 만든 행렬을 회전 후 그 앞의 값을 한 줄 추가하는 것을 1을 넣을 때까지 반복한다. A[::-1]를 하면 역순이 되고 zip하면 회전이 된다.
• 이런 풀이는 어떻게 떠올리는 것인지... 똑똑한 사람들 많다. 

||  =>  |9|  =>  |8|      |6 7|      |4 5|      |1 2 3|
                 |9|  =>  |9 8|  =>  |9 6|  =>  |8 9 4|
                                     |8 7|      |7 6 5|

def generateMatrix(self, n):
    A, lo = [], n*n+1
    while lo > 1:
        lo, hi = lo - len(A), lo
        A = [list(range(lo, hi))] + list(zip(*A[::-1]))
    return A

5. 배운 점

• (x, y)를 시계 방향 90도 회전 변환하면 (y, -x)가 된다는게 코드 짤 때도 유용하게 쓰인다. 
• zip을 이용한 마지막 풀이는 스스로 떠올리기 참 힘들 것 같긴한데.. 무튼 zip은 여기저기서 자주 사용된다. 회전시킬 때도 유용하다.