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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/68645

프로그래머스

풀이

2단계 문제이기에 코드 자체의 구현 난이도는 어렵지 않으나 풀이를 위한 아이디어를 생각하는 것이 난이도에 비해 어려웠다.

아이디어는 피라미드 모형으로 되어있는 예시의 배열을 아래처럼 좌측으로 붙여 정렬을 시키는 것이었다.

이렇게 좌측으로 정렬함으로써 배열을 채워나가는 로직을 생각하는 것이 훨씬 쉬워진다.

배열의 절반인 삼각형을 이루는 칸을 벗어나거나, 배열에 이미 값이 채워진 경우 채워가는 방향을 아래의 순서대로 반복하여 변경하면 나선형으로 피라미드를 모두 채울 수 있게 된다.

1. 아래로
2. 우측으로
3. 좌상향 대각선으로

이 순서대로 반복하며 (0, 0) 칸부터 숫자들을 채워보면

(1. 아래로) 1, 2, 3, 4를 채운 후 5를 채울 칸은 삼각형의 하단을 벗어나므로 방향을 전환한다.

(2. 우측으로) 5, 6, 7을 채운 후 8을 채울 칸은 삼각형의 우측 부분을 벗어나므로 방향을 전환한다.

(3. 좌상향 대각선으로) 8, 9를 채운 후 10을 채울 칸은 이미 채워져 있으므로 방향을 전환한다.

(다시 1. 아래로) 10을 채운다. n = 4일 때 모든 칸을 채웠으므로 종료한다.

 

아래는 위에서 설명한 로직을 구현한 코드이다.

def solution(n):
    dir = [[1, 0], [0, 1], [-1, -1]] # 다음에 나아갈 방향을 미리 지정
    answer = [[0 for _ in range(n)] for _ in range(n)]
    
    num = n * (n + 1) // 2 # 1부터 n까지의 합
    
    x = y = 0
    idx = 0 # dir의 index를 담당할 변수
    answer[x][y] = 1 # (0, 0)에 1을 채움
    
    for i in range(2, num + 1): # 2부터 num까지 반복
        dx, dy = dir[idx % 3] # 다음 칸으로 이동
        nx = x + dx
        ny = y + dy
        
        if nx < 0 or ny < 0 or nx > n - 1 or ny > n - 1 or answer[nx][ny] != 0: # 이동한 위치가 삼각형 밖이거나 이동한 위치가 이미 채워진 경우
            idx += 1 # 이동 방향을 변경
            
            dx, dy = dir[idx % 3] # 변경한 방향으로 이동
            nx = x + dx
            ny = y + dy
        
        x = nx
        y = ny
        answer[x][y] = i # 이동한 위치에 채우기   
        
    return [i for item in answer for i in item if i != 0] # 0으로 채워진 칸은 제외하고 반환