[Python] 정수를 나선형으로 배치하기

 

문제 분석

• 양의 정수 n
• n x n 배열에 1부터 n^2까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열 return

 

코드 설계

• 값을 채울 때, 끝까지 가는데 만약 값이 있으면 멈추고 방향 바꾸기
• 방향은 좌 - 하 - 우 - 상 순서

1	2	3	4
12	13	14	5
11	16	15	6
10	9	8	7

 

• (0,0) - (0,1) - (0,2) - (0,3) - (1,3) - (2,3) - (3,3) -  

 

• 아니면 크기가 4일때, 4- 3- 3- 2- 2- 1- 1 로 채우기

~ 하면 회전, ~ 하면 회전 --

 

정답 코드

실패..

def solution(n):
    answer = [[]]
    n = [[0] * n for _ in range(n)]
    v = [[False] * n for _ in range(n)]
    
    dh = [1, 0, -1, 0]
    dw = [0, 1, 0, -1]
    
    cnt = 0
    
    while cnt <= n**2 : 
        if 
    
    
    return answer

 

다른 사람 코드 1

def solution(n):
    answer = [[None for j in range(n)] for i in range(n)]
    move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    x, y, m = 0, 0, 0
    for i in range(1, n**2 + 1):
        answer[y][x] = i
        if y + move[m][0] >= n or x + move[m][1] >= n or answer[y + move[m][0]][x + move[m][1]]:
            m = (m + 1) % len(move)
        y, x = y + move[m][0], x + move[m][1]
    return answer

 

def solution(n):
    answer = [[None] * n for _ in range(n)]
    move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    x, y, m = 0, 0, 0
    for i in range(1, n**2 + 1):
        answer[y][x] = i
        if y + move[m][0] >= n or x + move[m][1] >= n or answer[y + move[m][0]][x + move[m][1]]:
            m = (m + 1) % len(move)
        y, x = y + move[m][0], x + move[m][1]
    return answer

 

GPT

def solution(n):
    # 결과 배열 초기화
    answer = [[0] * n for _ in range(n)]
    
    # 초기값 설정
    num = 1  # 배열에 채울 숫자
    top, bottom, left, right = 0, n - 1, 0, n - 1  # 경계 설정

    while num <= n * n:
        # 1. 위쪽 → 오른쪽으로 이동
        for i in range(left, right + 1):
            answer[top][i] = num
            num += 1
        top += 1  # 위쪽 경계 줄이기

        # 2. 오른쪽 → 아래쪽으로 이동
        for i in range(top, bottom + 1):
            answer[i][right] = num
            num += 1
        right -= 1  # 오른쪽 경계 줄이기

        # 3. 아래쪽 → 왼쪽으로 이동
        for i in range(right, left - 1, -1):
            answer[bottom][i] = num
            num += 1
        bottom -= 1  # 아래쪽 경계 줄이기

        # 4. 왼쪽 → 위쪽으로 이동
        for i in range(bottom, top - 1, -1):
            answer[i][left] = num
            num += 1
        left += 1  # 왼쪽 경계 줄이기

    return answer

동작 원리

1. 초기화:
   • answer는 n x n 크기의 2차원 리스트로, 모두 0으로 초기화됩니다.
   • top, bottom, left, right는 나선형 경계(위, 아래, 왼쪽, 오른쪽)를 나타냅니다.
   • num은 배열에 채워질 숫자로, 1부터 시작하여 n²까지 증가합니다.
2. 반복:
   • 반복문을 사용하여 num이 n²보다 작거나 같을 때까지 숫자를 배열에 채웁니다.
   • 각 반복 단계에서 나선형으로 숫자를 채우며, 경계를 업데이트합니다:
     1. 위쪽 → 오른쪽: top 행을 채우고, top 경계를 줄입니다.
     2. 오른쪽 → 아래쪽: right 열을 채우고, right 경계를 줄입니다.
     3. 아래쪽 → 왼쪽: bottom 행을 채우고, bottom 경계를 줄입니다.
     4. 왼쪽 → 위쪽: left 열을 채우고, left 경계를 줄입니다.
3. 종료 조건:
   • num > n²일 때 반복문을 종료하고 결과를 반환합니다.

 

시간 복잡도

• O(n²): 모든 n × n 요소를 한 번씩 채우므로 시간 복잡도는 O(n²)입니다.

 

코드 간결화 (파이썬다운 방식)

만약 경계를 직접 관리하지 않고, 이동 방향을 계산하는 방식으로 구현하려면 다음과 같이 작성할 수도 있습니다:

def solution(n):
    answer = [[0] * n for _ in range(n)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 이동 방향 (오른쪽, 아래, 왼쪽, 위)
    num, x, y, d = 1, 0, 0, 0  # 시작 숫자, 현재 위치, 방향 인덱스

    while num <= n * n:
        answer[x][y] = num
        num += 1
        nx, ny = x + directions[d][0], y + directions[d][1]

        # 다음 위치가 배열 범위를 벗어나거나 이미 채워졌으면 방향 전환
        if nx < 0 or ny < 0 or nx >= n or ny >= n or answer[nx][ny] != 0:
            d = (d + 1) % 4
            nx, ny = x + directions[d][0], y + directions[d][1]

        x, y = nx, ny

    return answer

이 방식도 동일한 결과를 출력하며, 나선형 이동의 논리를 간결하게 표현할 수 있습니다.