[python3] 정수를 나선형으로 배치하기 (프로그래머스)

 

문제만 읽으면 아 그렇구나~ 했는데 막상 코드로 옮기려니 머리가 아팠다.

2차원 배열에 아직 익숙하지 않아서 row col 이러다가 으아아아ㅏㅏ 하고 말았던..

관련 풀이를 많이 찾아봤는데 여전히 너무 복잡한 풀이 방식이었고 가장 괜찮은 풀이법을 찾아서 정리해보려고 한다.

 

입출력 예시를 보면 행, 열을 표로 그려놨는데, 여기서 행을 i, 열을 j라고 하자.

첫번째 칸에는 1이 들어간다. 이 숫자는 n *n의 값에 도달할 때 까지 계속 1씩 증가한다.

-> cnt라는 변수로 만들자.

 

cnt의 증가를 따라가보면 우측으로 가다가, 마지막 열에 닿았을 때 아래로 내려가고, 마지막 행에 닿았을 때 왼쪽으로 이동하고

맨 처음 열에 닿으면 위로 올라간다. ➡️ ⬇️ ⬅️ ⬆️의 순서인 것이다.

(이동의 순서가 있고, 이동 범위에 한계가 있다 !)

 

하나씩 보자면

➡️ i는 그대로 있고 j만 1씩 증가한다. (즉 열의 값이 채워진다.)

⬇️ j는 그대로 있고 i만 1씩 증가한다. (즉 각행의 마지막 열에 값이 채워진다.)

⬅️ i는 그대로 있고 j만 1씩 감소한다. (즉 행의 값이 역순으로 채워진다.)

⬆️ j는 그대로 있고 i만 1씩 감소한다. (즉 각 행의 첫번째 열에 값이 채워진다.)

 

여기서 가만히 있는 것은 0, 증가는 1, 감소는 -1이라 하면

아래와 같은 배열로 표현할 수 있다.(d는 direction의 약자)

➡️ ⬇️ ⬅️ ⬆️

di = [0, 1, 0, -1]

dj = [1, 0, -1, 0]

 

이제 방향 전환이 필요하다면 di,dj의 다음 인덱스 값을 활용하면 된다.

 

그런데 한바퀴 돌고나면 0,0자리에는 1이 있기 때문에 다시 오른쪽으로 가야한다. 

즉 이동할 자리에 숫자가 차있는지 확인해야 하는 것이다. ( 숫자가 없어야 이동해서 채울 수 있으니까)

(이동하기 전에 값이 있는 지 확인해야 한다 !)

 

그리고 최종적으로는 cnt의 값이 n *n이 됐을 때 함수는 종료되어야 한다.

(마지막 숫자를 채우면 끝!)

 

이제 이걸 코드로 옮겨본다.

def solution(n):
    # 채울 칸
    arr = [[0] * n for _ in range(n)]
    # 좌표, 채울 숫자
    i, j, cnt = 0, 0, 1
    # 방향
    dr = 0
    di = [0, 1, 0, -1]
    dj = [1, 0, -1, 0]
    
    #첫번째 칸을 채워주자.(시작점 정의, 방향 설정, 무한 루프 방지)
    arr[i][j] = cnt
    cnt += 1
    #cnt가 n*n이 될 때까지 반복함.
    while cnt <= n * n:
        # 이동 준비를 한다.
        ni, nj = i + di[dr], j + dj[dr]
        # 이동 할 위치가 범위 내이고 다음 값이 0인지 확인한다.
        if 0 <= ni < n and 0 <= nj < n and arr[ni][nj] == 0:
            #조건을 다 만족했으니 이동 후 증가시킨 값을 넣어준다.
            i, j = ni, nj
            arr[i][j] = cnt
            cnt += 1
        else:
            #방향 전환을 해준다. (범위를 벗어나거나, 다음 자리에 값이 있는 경우니)
            dr = (dr + 1) % 4
            # index out of range 방지: 4로 나눈 나머지를 할당(0,1,2,3)
    
    return arr