문제 소개
양의 정수 n이 주어졌을 때, 1부터 n²까지의 숫자를 시계 방향으로 나선형(spiral) 순서에 따라 채워 넣은 n×n 정사각형 행렬을 생성하는 것이 이번 문제의 목표입니다. 예를 들어 n = 4라면 다음과 같은 행렬이 완성됩니다.
| 1 | 2 | 3 | 4 |
| 12 | 13 | 14 | 5 |
| 11 | 16 | 15 | 6 |
| 10 | 9 | 8 | 7 |
숫자 1에서 출발해 첫 번째 행을 따라 오른쪽으로 이동하고, 행렬의 끝에 도달하면 아래로 방향을 꺾습니다. 이후 왼쪽, 위쪽으로 돌아오면서 점점 안쪽으로 나선을 그리듯 채워 나가는 방식입니다.
알고리즘 접근 방식
가장 직관적인 해법은 행렬의 네 변을 하나의 '겹(layer)'으로 보고, 바깥겹부터 차례대로 채워 나간 뒤 경계를 안쪽으로 좁혀 가는 것입니다. 네 개의 경계 변수를 활용하면 깔끔하게 구현할 수 있습니다.
- (row1, col1) := (0, 0), (row2, col2) := (n, n)으로 초기화하고, 모든 원소가 0인 n×n 크기의 결과 행렬 res를 생성한 뒤 num := 1로 설정합니다.
- num ≤ n²인 동안 다음 네 단계를 반복합니다.
- 윗변: col1부터 col2-1까지 왼쪽→오른쪽으로 res[row1][i]에 num을 채우고 1씩 증가시킵니다. num > n²이 되면 즉시 중단합니다.
- 오른쪽 변: row1+1부터 row2-1까지 위→아래로 res[i][col2-1]을 채웁니다.
- 아랫변: col2-2부터 col1까지 역순으로, 즉 오른쪽→왼쪽으로 res[row2-1][i]를 채웁니다.
- 왼쪽 변: row2-2부터 row1+1까지 역순으로, 즉 아래→위로 res[i][col1]을 채웁니다.
- 한 바퀴를 돌고 나면 row1과 col1은 1씩 증가시키고, row2와 col2는 1씩 감소시켜 다음 안쪽 겹으로 이동합니다.
- 모든 칸이 채워지면 res를 반환합니다.
파이썬 구현 코드
다음 코드를 통해 실제 동작을 확인해 보겠습니다.
class Solution(object):
def generateMatrix(self, n):
row1, col1 = 0, 0
row2, col2 = n, n
result = [[0] * n for _ in range(n)]
num = 1
while num <= n ** 2:
# 윗변: 왼쪽 → 오른쪽
for i in range(col1, col2):
result[row1][i] = num
num += 1
if num > n ** 2:
break
# 오른쪽 변: 위 → 아래
for i in range(row1 + 1, row2):
result[i][col2 - 1] = num
num += 1
if num > n ** 2:
break
# 아랫변: 오른쪽 → 왼쪽
for i in range(col2 - 2, col1 - 1, -1):
result[row2 - 1][i] = num
num += 1
if num > n ** 2:
break
# 왼쪽 변: 아래 → 위
for i in range(row2 - 2, row1, -1):
result[i][col1] = num
num += 1
# 경계를 안쪽으로 한 칸씩 이동
row1 += 1
row2 -= 1
col1 += 1
col2 -= 1
return result
ob1 = Solution()
print(ob1.generateMatrix(4))
실행 결과
입력:
4
출력:
[[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]
복잡도 분석
- 시간 복잡도: O(n²) — 행렬의 각 칸을 정확히 한 번씩만 방문하므로 전체 원소 개수에 비례합니다.
- 공간 복잡도: O(n²) — 결과 행렬 자체를 저장해야 하며, 출력 공간을 제외하면 추가로 사용되는 메모리는 O(1)입니다.