문제

[프로그래머스] 삼각 달팽이 (LV. 2)

요약

  • 1 ~ 1000 사이의 숫자 n 이 주어지면, 정삼각형의 한 꼭짓점에서 시작해, 반시계 방향 나선형으로 1부터 순서대로 숫자를 써 넣는다. 그 결과를 반환한다.

분류

  • 배열
  • dx/dy

풀이

1. 내 풀이

  • 발상 : 최대한 직관적으로 생각했다. 문제에서 주어진 행동을 실제로 행하며, 결과를 구했다. 이는 문제에서 n 값의 범위를 1 ~ 1000 으로 제한하고 있기에 가능했다. 최악의 경우(n = 1000)에도 리스트 요소의 개수가 (1000 * 1001) // 2 = 50,000,500 이었기에 감당할만 했다. n 제한이 없었다면 이차원 리스트를 사용하는 것도 부담스러웠을 것이다.
  • 사방으로 방향_cur 이라는 커서를 변수로 선언하고, 각각 관리했는데, 조금은 깔끔하지 않아 보인다.
  • 마지막에 2차원 배열 1차원으로 풀 때, 이중 컴프리헨션(?)을 해야하는데, 그때 두 for 문의 순서에 유의하자.


def solution(n):
    arr = [[0] * j for j in range(1, n + 1)]

    left_cur = 0; down_cur = n - 1; right_cur = -1; up_cur = 0

    max_num = (n * (n + 1)) // 2
    current_num = 0
    dis = n

    arr[0][0] = 1

    while True:
        #goDown
        for i in range(up_cur, up_cur + dis):
            current_num += 1
            arr[i][left_cur] = current_num
        dis -= 1
        up_cur += 2
        left_cur += 1
        if current_num == max_num : break

        #goRight
        for i in range(left_cur, left_cur + dis):
            current_num += 1
            arr[down_cur][i] = current_num
        dis -= 1
        down_cur -= 1
        if current_num == max_num : break

        #goUp
        for i in range(down_cur, down_cur - dis, -1):
            current_num += 1
            arr[i][right_cur] = current_num
        dis -= 1
        right_cur -= 1
        if current_num == max_num : break

    return [val for arr_val in arr for val in arr_val]


2. 프로그래머스 좋아요가 많았던 풀이

  • 발상 : 전형적인 dx, dy. 한 문제에 여러 풀이를 알아두는 것은 중요하다. 
def solution(n):
    dx = [0, 1, -1]; dy=[1, 0, -1]

    b = [[0] * i for i in range(1, n + 1)]

    x, y = 0, 0
    num = 1
    d = 0

    while num <= (n + 1) * n // 2:
        b[y][x] = num
        ny = y + dy[d]
        nx = x + dx[d]
        num+=1

        if 0 <= ny < n and 0 <= nx <= ny and b[ny][nx]== 0:
            y, x = ny, nx
        else:
            d = (d + 1) % 3
            y += dy[d]
            x += dx[d]
    return sum(b,[])


3. 최적화 풀이

  • <취업과 이직을 위한 프로그래머스 코딩테스트 문제 풀이 전략> 을 참고한 코드입니다. (링크)
  • 발상 : dx, dy 와 발상은 비슷하다. 그러나 for 문 범위를 지정하는 부분과 if 문 조건 처리 부분에서 고수의 향기가 물씬 난다. 배워두자. 
def solution(n):
    res = [[0] * i for i in range(1, n+1)]
    y, x = -1, 0
    num = 1

    for i in range(n):
        for _ in range(i, n):
            angle = i % 3
            # 순서대로 아래 -> 오른쪽 -> 위 (반시계 나선형)
            if angle == 0: y += 1
            elif angle == 1: x += 1
            elif angle == 2: y -= 1; x -= 1
            res[y][x] = num
            num += 1

    return [i for j in res for i in j]