Construct a square matrix with a size N × N containing integers from 1 to N * N in a spiral order, starting from top-left and in clockwise direction.

Example

For n = 3, the output should be

solution(n) =
[[1, 2, 3],
[8, 9, 4],
[7, 6, 5]]

Input/Output

[execution time limit] 4 seconds (py3)

[input] integer n

Matrix size, a positive integer.

Guaranteed constraints:
3 ≤ n ≤ 100.

[output] array.array.integer

n에 따라 돌아가면서 번호를 넣어줘야 하는 문제이다.

처음에는 관련된 수학 공식 혹은 규칙이 있을 줄 알았다.
규칙은 있었지만 적용해야하는 공간이 계속해서 달라지면서 코드를 어떻게 짜야 할지 고민이었다.

Solution

def solution(n):
    m = [[0] * n for i in range(n)]
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
    x, y, c = 0, -1, 1
    for i in range(n + n - 1):
        for j in range((n + n - i) // 2):
            x += dx[i % 4]
            y += dy[i % 4]
            m[x][y] = c
            c += 1
    return m

Ex) n=3

m =
[[0,0,0],
[0,0,0],
[0,0,0]]

i=0, j=0
""" 1 번째 반복문 """
x += dx[0] # x = 0
y += dy[0] # y = 0
m[0][0] = 1

i=0, j=1
""" 2 번째 반복문 """
x += dx[0] # x = 0
y += dy[0] # y = 1
m[0][1] = 2

i=0, j=2
""" 3 번째 반복문 """
x += dx[0] # x = 0
y += dy[0] # y = 2
m[0][2] = 3

i=1, j=0
""" 4 번째 반복문 """
x += dx[1] # x = 1
y += dy[1] # y = 2.
m[1][2] = 4

...

나는 회전의 방향에 따라 cnt를 조절해 만들 생각을 했었는데
배열의 index를 이용해 이렇게 만들어 주는 것에 크게 놀랐다...

해결 방법이 여러가지이므로 다양한 해설을 봐보고, 지식도 많이 접해서 꼭 문제를 보고 여러 가지 해결방법을 떠올릴 수 있는 사람이 되겠다.