[알고리즘] Programmers 삼각 달팽이 #Python

김상현·2022년 12월 26일
0

알고리즘

목록 보기
252/301
post-thumbnail

[Programmers] 삼각 달팽이 바로가기

📍 문제 설명

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.


📍 제한사항

  • n은 1 이상 1,000 이하입니다.

📍 입출력 예

nresult
4[1,2,9,3,10,8,4,5,6,7]
5[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

📍 입출력 예 설명

입출력 예 #1

  • 문제 예시와 같습니다.

입출력 예 #2

  • 문제 예시와 같습니다.

입출력 예 #3

  • 문제 예시와 같습니다.

📍 풀이

  • 달팽이 채우기를 진행할 때 숫자가 채워지는 이동 방향은 총 3가지 방향이 있다.
    • 첫 번째 이동 방향은 현재 위치에서 아래 방향의 이동이다.
      • 그래프 기준 y 축 방향으로 1 증가하는 방식으로 진행된다.
    • 두 번째 이동 방향은 현재 위치에서 오른쪽 방향의 이동이다.
      • 그래프 기준 x 축 방향으로 1 증가하는 방식으로 진행된다.
    • 세 번째 이동 방향은 현재 위치에서 왼쪽 위 대각선 방향의 이동이다.
      • 그래프 기준 x 축, y 축 방향으로 각각 1씩 증가하는 방식으로 진행된다.
  • 3가지 방향으로 이동할 때 이동 거리는 n, n-1, n-2, ... 3, 2, 1로 1씩 감소한다.
  • 위 조건을 이용하여 그래프를 생성하고 그래프의 값을 초기화한다.

📌 문제 풀이

✏️ [1] 그래프 초기화

triangularSnail = [[0] * (i+1) for i in range(n)]
  • triangularSnail 는 삼각 달팽이의 값을 저장할 그래프이다.

✏️ [2] 삼각 달팽이 이동

for i in range(n, 0, -1):
    if direction == 0:
        for _ in range(i):
            y += 1
            triangularSnail[y][x] = num
            num += 1
    elif direction == 1:
        for _ in range(i):
            x += 1
            triangularSnail[y][x] = num
            num += 1
    elif direction == 2:
        for _ in range(i):
            x, y = x - 1, y - 1
            triangularSnail[y][x] = num
            num += 1
    direction = (direction + 1) % 3
  • direction 은 이동 방향이다.
  • 각 이동 방향에 맞추어 이동 거리(i) 만큼 이동하면서 triangularSnail 그래프의 값을 갱신한다.
    • direction : 0인 경우는 그래프 기준 아래 방향으로 이동한다.
      • y 값을 1 증가시키면서 triangularSnail 그래프의 값을 갱신한다.
    • direction : 1인 경우는 그래프 기준 오른쪽 방향으로 이동한다.
      • x 값을 1 증가시키면서 triangularSnail 그래프의 값을 갱신한다.
    • direction : 2인 경우는 그래프 기준 왼쪽 위 방향으로 이동한다.
      • x, y 값을 각각 1 감소시키면서 triangularSnail 그래프의 값을 갱신한다.

✍ 코드

def solution(n):
    triangularSnail = [[0] * (i+1) for i in range(n)]
    x, y, num, direction = 0, -1, 1, 0
    
    for i in range(n, 0, -1):
        # 왼쪽 아래 대각선 방향
        if direction == 0:
            for _ in range(i):
                y += 1
                triangularSnail[y][x] = num
                num += 1
        # 오른쪽 방향
        elif direction == 1:
            for _ in range(i):
                x += 1
                triangularSnail[y][x] = num
                num += 1
        # 왼쪽 위 대각선 방향
        elif direction == 2:
            for _ in range(i):
                x, y = x - 1, y - 1
                triangularSnail[y][x] = num
                num += 1
        direction = (direction + 1) % 3
        
    return sum(triangularSnail, [])
profile
목적 있는 글쓰기

0개의 댓글