프로그래머스 -정수를 나선형으로 배치하기- 리뷰

--내가 제출한 기존 코드 --

def solution(n):
    answer = [[0 for _ in range(n)] for _ in range(n)]
    val = 1
    x = 0
    y = 0
    direction = 'x'
    x_locator = 1
    y_locator = 1
    x_limit = n - 1
    y_limit = n - 2
    x_cnt = 0
    y_cnt = 0
    while val <= n**2:
        answer[y][x] = val
        if direction == 'x':
            if x_cnt == x_limit:
                x_limit -= 1
                direction = 'y'
                y += y_locator
                x_locator *= -1
                x_cnt = 0
                val += 1
                continue
            x += x_locator
            x_cnt += 1
            
        else:
            if y_cnt == y_limit:
                y_limit -= 1
                direction = 'x'
                x += x_locator
                y_locator *= -1
                y_cnt = 0
                val += 1
                continue
            y += y_locator
            y_cnt += 1
        val += 1
        
	return answer

* 리뷰 이유: 문제는 풀었으나 너무나 비효율 적인 방법(1차원 공간에 국한된 사고방식)으로 풀었고, 순환하는 규칙을 다루는 법을 익혀두면 다른 문제에도 적용 가능하다고 판단해서

* 2차원 공간 문제는 2차원 리스트를 적극 활용하자.

* 순환하는 규칙은 나머지 계산을 적극 활용하자.

* 좌표 이동은 [y 증감값, x 증감값]으로 구성된 2차원 리스트를 활용하면 코드를 간결하게 작성할 수 있다.

 

-- 모범 코드 (출처: 프로그래머스 다른 사람 풀이) --

def solution(n):
    # 모든 요소가 None으로 초기화된 n*n 그리드 생성
    answer = [[None for j in range(n)] for i in range(n)]

    # 움직임의 순서를 정의 (우, 하, 좌, 상)
    move = [[0, 1], [1, 0], [0, -1], [-1, 0]]

    # 현재 위치 (y, x)와 움직임의 방향 (m) 초기화
    y, x, m = 0, 0, 0

    # 1부터 n*n까지의 수를 나선형으로 그리드에 채워 넣음
    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

* 달팽이 문제의 방향 규칙은 아래의 네 규칙이 계속 반복되는 형태이다.

1. 우

2. 하

3. 좌

4. 상

 

* move는 규칙에 따른 y, x 증감값을 규정한 리스트이다.

ex1) move[0][0] = 첫 번째 방향: '우'에 따르는 y 증감값 = 0, move[0][1] = 첫 번째 방향: '우'에 따르는 x 증감값 = 1

ex2) move[1][0] = 두 번째 방향: '하'에 따르는 y 증감값 = 1, move[1][1] = 두 번째 방향: '하'에 따르는 x 증감값 = 0,

.

.

.

 

* m = (m + 1) % len(move)

순환되는 규칙이 있다면 방향이 아닌 다른 문제에도 사용할 수 있는 공식이다.

len(move)를 순환 주기 숫자로 바꿔 주면 된다.

달팽이 문제는 4방향 이동이므로 len(move)는 4가 된다.

m의 변화 값을 직접 눈으로 확인해 보자.

ex) m의 초기값은 0 이며 순환 주기는 4 인경우

m = 0 -> 0

m = (0 + 1) % 4 -> 1

m = (1 + 1) % 4 -> 2

m = (2 + 1) % 4 -> 3

-- 순환 지점 --

m = (3 + 1) % 4 -> 0

m = (0 + 1) % 4 -> 1

.

.

.

이런식으로 0, 1, 2, 3을 계속 순환하게 된다.

때문에 move[m]은 우, 하, 좌, 상 의 나선형 움직임을 의미한다.