프로그래머스 파이썬 기초 트레이닝 :: 정수를 나선형으로 배치하기 (*)
문제 설명
프로그래머스 URL
https://school.programmers.co.kr/learn/courses/30/lessons/181832
프로그래머스 코딩 카테고리
코딩 기초 트레이닝
Day 25 - 정수를 나선형으로 배치하기
Lv.0
문제 내용
양의 정수 n이 매개변수로 주어집니다. n × n 배열에 1부터 n2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 return 하는 solution 함수를 작성해 주세요.
넘나 어려운 문제다..
-----------------------------------
나선형으로 도는거기 때문에, 시계방향으로 돈다.
방향은 R → D → L → U 이렇게 고정이 되어있다.
4가지 경우에 따른 방향 설정
dir = R(1) → D(2) → L(3) → U(4)
def solution(n):
answer = [[0]*n for i in range(n)]
x, y = 0, 0
dir = 'r' #dir로 방향조정 : r, d, l, u
if n == 1:
return [[1]]
for i in range(1, n*n+1):
answer[x][y] = i
if dir == 'r':
y += 1
if y == n-1 or answer[x][y+1] != 0:
dir = 'd'
elif dir == 'd':
x += 1
if x == n-1 or answer[x+1][y] != 0:
dir = 'l'
elif dir == 'l':
y -= 1
if y == 0 or answer[x][y-1] != 0:
dir = 'u'
elif dir == 'u':
x -= 1
if x == n-1 or answer[x-1][y] != 0:
dir = 'r'
return answer1) 1 X 1 배열일때
if n == 1:
return [[1]]n이 1일때를 따로 지정해주지 않으면 테스트13에서 "실패 (런타임 에러)"로 뜸
그 이유는 x, y = 0, 0으로 선언하면 반복문을 시작한 r 방향때 부터 문제가 생긴다.
if dir == 'r':
y += 1
if y == n-1 or answer[x][y+1] != 0:
dir = 'd'y+=1 을 하는데 arr[0][0]을 입력하지않고, 바로 arr[0][1] 값부터 넣는데,
y+=1 을 수행한 이후기 때문에 if y ==n-1 이 항상 참이 되기 때문이다.
그래서 arr[0][0] 이 입력되지도 않아도 r 방향의 if문이 참이 되서 런타임 에러뜸
2) r : 행은 그대로고, 열만 오른쪽으로 이동
for i in range(1, n*n+1):
answer[x][y] = i
if dir == 'r':
y += 1
if y == n-1 or answer[x][y+1] != 0:
ir = 'd'행은 그대로이기 때문에 answer[x][y] 에서 x축은 그대로고, y축만 +1 씩 이동
이동한 y축이 배열의 끝까지 도착했을때나, 이미 answer 다음자리에 값이 들어가있으면 방향전환
3) d : 열은 그대로고, 행만 위에서 아래로 이동
elif dir == 'd':
x += 1
if x == n-1 or answer[x+1][y] != 0:
dir = 'l'열은 그대로이기 때문에 answer[x][y] 에서 y축은 그대로고, x축만 +1 씩 이동
동작이 멈추는 원리는 r때랑 동일
4) l : 행은 그대로고, 열만 오른쪽에서 왼쪽으로 이동
elif dir == 'l':
y -= 1
if y == 0 or answer[x][y-1] != 0:
dir = 'u'행은 그대로이기 때문에 answer[x][y] 에서 x축은 그대로고, y축만 -1 씩 이동
5) u : 열은 그대로고, 행만 밑에서 위로 이동
elif dir == 'u':
x -= 1
if x == 0 or answer[x-1][y] != 0:
dir = 'r'열은 그대로이기 때문에 answer[x][y] 에서 y축은 그대로고, x축만 -1 씩 이동
방향전환을 숫자로 지정해도됨 (원리는 동일)
def solution(n):
arr = [[0]*n for i in range(n)]
x, y = 0, 0
mode = 1 #mode로 방향조정 : R(1)-> D(2) -> L(3) -> U(4)
if n == 1:
return [[1]]
for i in range(1, n*n+1):
arr[x][y] = i
if mode%4 == 1:
y+=1
if y == n-1 or arr[x][y+1] != 0:
mode+=1
elif mode%4 == 2:
x+=1
if x == n-1 or arr[x+1][y] != 0:
mode+=1
elif mode%4 == 3:
y-=1
if y == n-1 or arr[x][y-1] != 0:
mode+=1
elif mode%4 == 0:
x-=1
if x == n-1 or arr[x-1][y] != 0:
mode+=1
return arr-----------------------------------
R → D → L → U 순환하는건 고정이고, 과정마다 x축과 y축의 인덱스 변화를 표현하면 이렇다.
x축은 R : 변화없음 → D : +1씩 증가 → L : 변화없음 → U : -1씩 감소
y축은 R : +1씩 증가 → D : 변화없음 → L : -1씩 감소 → U : 변화없음
이거를 배열로 표현하면 x축 = [0, 1, 0, -1], y축 = [1, 0, -1, 0]
x, y 축 배열을 설정
x축 y축 배열을 활용해서 인덱스를 만듬
def solution(n):
answer = [[0]*n for _ in range(n)]
dx=[0, 1, 0, -1]
dy=[1, 0, -1, 0]
x, y=0, 0
answer[x][y] = 1
k = 2
while k <= n*n:
for i in range(4):
while True:
nx = x + dx[i]
ny = y + dy[i]
if nx>=n or ny>=n or nx<0 or ny<0 or answer[nx][ny]!=0:
break
else:
answer[nx][ny] = k
x = nx
y = ny
k += 1
return answer1) 1 X 1 배열일때
dx=[0, 1, 0, -1]
dy=[1, 0, -1, 0]
x, y = 0, 0이렇게 선언을 하고 반복문을 했을때
제일 첫번째 수가 answer[0+0][1+0] 이렇게 되서, 이 코드 또한 answer[0][0]은 건너뛰기가 된다.
answer[x][y]=1그래서 answer[0][0] 값을 이렇게 지정해줘도된다.
2) 세개의 반복문
while k <= n*n:
for i in range(4):
while True:
nx = x + dx[i]
ny = y + dy[i]
if nx>=n or ny>=n or nx<0 or ny<0 or answer[nx][ny]!=0:
break
else:
answer[nx][ny] = k
x = nx
y = ny
k += 1① 반복문 : while k <= n*n:
k 값이 2부터 시작해 n*n 배열을 다 채울때까지 반복됨
② 반복문 : for i in range(4):
x축, y축 배열의 방향이 4개라서 4번 반복한다.
우, 하, 좌, 상 순서로 이동하기 위한 방향을 나타낸다
③ 반복문 : while True:
②의 for문에서 방향을 정했으면, 그 한쪽 방향으로 계속 이동하는 무한 루프이다.
다음 배열 인덱스에 값이 이미 차있거나, 배열의 경계를 벗어날려고 하면 반복문을 종료하고 다음 방향으로 전환한다.
while True:
nx = x + dx[i]
ny = y + dy[i]
if nx>=n or ny>=n or nx<0 or ny<0 or answer[nx][ny]!=0:
break
else:
answer[nx][ny] = k
x = nx
y = ny
k += 1else문에서는 인덱스 값에 k를 저장시킨다.
다음 반복문이 돌때 x, y 값을 이어가기 위해서 x, y = nx, ny로 선언
-----------------------------------
위의 코드에서는 while, for문을 사용해서 x축 y축 배열의 인덱스를 옮겨갔는데
반복문 대신 dir의 숫자를 활용해서 인덱스에 접근을 할 수 있다.
x, y 축 배열 인덱스를 활용
반복문을 최소화 할 수 있음
def solution(n):
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
x, y = 0, -1
arr = [[0] * n for _ in range(n)]
k = 1
dir = 0
while k <= n**2:
nx = x + dx[dir]
ny = y + dy[dir]
if 0 <= nx < n and 0 <= ny < n and not arr[nx][ny]:
arr[nx][ny] = k
k += 1
x, y = nx, ny
else:
dir = (dir + 1) % 4
return arr1) 1 X 1 배열일때
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
x, y = 0, -1x, y = 0, -1 로 선언을 했기때문에
answer[0+0][1-1] = answer[0][0] 값 부터 시작을 한다.
그래서, 이렇게 x, y를 선언하면 별도로 answer[0][0]일때 값을 주지 않더라도 테스트 13에서 런타임 에러가 나지않음
while k <= n**2:
nx = x + dx[dir]
ny = y + dy[dir]
if 0 <= nx < n and 0 <= ny < n and not arr[nx][ny]:
arr[nx][ny] = k
k += 1
x, y = nx, ny
else:
dir = (dir + 1) % 4
dir = (dir + 1) % 4 로 방향을 전환하기때문에 방향을 전환해주는 for문 - range(4)가 필요없게된다.
그리고, if문에서 0 <= nx < n and 0 <= ny < n and not arr[nx][ny] 배열 범위가 넘어가지 않고 값이 0일때를 조건문 걸어둘 수 있다.
같은 의미 : nx < n and ny < n and nx >= 0 and ny >= 0 and answer[nx][ny] == 0
-----------------------------------
이동을 하는 배열을 이차원 배열로 둬서, x축 y축을 하나의 배열에서 수행할 수도 있다.
x, y 축 2차원 배열
x, y축을 나타내는 2차원 배열과 방향을 조절하는 m 변수
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[x][y] = i
if x + move[m][0] >= n or y + move[m][1] >= n or answer[x + move[m][0]][y + move[m][1]]:
m = (m + 1) % 4
x = x + move[m][0]
y = y + move[m][1]
return answeranswer[x][y]로 값부터 넣은 뒤에
if문으로 배열 인덱스 범위, 배열 값 체크한 뒤에 방향을 전환한다.
입력 가능한 상태면 move 2차원배열의 인덱스를 더해서 answer[x][y] 인덱스를 변화시킴
댓글
댓글 쓰기