문제
홀수 N이 주어질 때, N×N 배열의 중앙에서 시작하여 위→오른쪽→아래→왼쪽 순서로 나선형으로 1부터 N²까지 채운다. 배열을 출력하고 주어진 수의 위치를 출력한다.
입력
첫째 줄에 홀수 N, 둘째 줄에 찾을 수가 주어진다.
출력
N×N 배열과 찾은 수의 행, 열 번호(1-indexed)를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 2 | 7 8 9 6 1 2 5 4 3 2 3 |
풀이
중앙에서 시작하여 방향 전환 규칙에 따라 나선형으로 배열을 채운다.
- 중앙 좌표 (N//2, N//2)에서 시작하여 1부터 순서대로 값을 채운다
- 이동 방향은 위→오른쪽→아래→왼쪽 순서로 전환한다
- 이동 거리는 방향을 2번 전환할 때마다 1씩 증가한다
- N²개를 모두 채우면 종료하고 배열을 출력한다
- 찾는 수의 위치를 탐색하여 출력한다
핵심 아이디어: 나선형 이동에서 이동 거리가 1, 1, 2, 2, 3, 3, ...으로 증가하는 패턴을 이용하여 시뮬레이션한다.
코드
N = int(input())
target = int(input())
x = y = N // 2
array = [[""] * N for _ in range(N)]
direction = [(0, -1), (1, 0), (0, 1), (-1, 0)]
move = 1
index = 0
num = 1
while True:
for _ in range(move):
array[y][x] = num
num += 1
x += direction[index][0]
y += direction[index][1]
index = (index + 1) % 4
if index % 2 == 0:
move += 1
if num > N * N:
break
for i in range(N):
for j in range(N):
print(array[i][j], end = " ")
print()
for i in range(N):
for j in range(N):
if array[i][j] == target:
print(i + 1, j + 1)
exit()복잡도
- 시간: O(N²) — N×N 배열 채우기 및 출력
- 공간: O(N²) — N×N 배열