[python] 프로그래머스 삼각 달팽이

링크

programmers.co.kr/learn/courses/30/lessons/68645

코딩테스트 연습 - 삼각 달팽이

설명

달팽이 숫자 만들기의 삼각형 버전이다. 반시계방향으로 숫자를 채워나가야 한다.

n 범위가 ~1000 이므로 n = 1000 일때의 시도횟수가 대략 몇회인지 고민을 먼저했다.

n에 따른 삼각형 네모칸의 갯수는 n(n+1) / 2 와 같다. 대략 1000일때 50만번 카운팅 하면 된다.

DFS/BFS 처럼, dx와 dy를 통해 삼각형 배열의 움직이는 방향을 지정했다.

삼각형을 사각 격자판에 배치하면 아래와 같이 배열된다.

이를 응용해, 전체 칸의 갯수만큼 배열을 채울 때 까지, 반시계방향으로 배열을 채워나가면 삼각 달팽이 숫자가 완성될 것이다.

 

 

코드

def solution(n):
    dx = [1,0,-1]
    dy = [0,1,-1]
    board = [[0]*(n) for _ in range(n)]
    
    answer = []
    next = board[0][0]
    cnt = 1
    i,j = 0,0
    d = 0
    ran = (n*(n+1)) // 2
    while ran >= cnt:
        if  0 <= i < n and 0 <= j < n and board[i][j] == 0 :
            board[i][j] = cnt
            cnt += 1
        else:
            i -= dx[d]
            j -= dy[d]
            d = (d+1) % 3
        i += dx[d]
        j += dy[d]
    
    for i in range(n):
        for j in range(0,i+1):
            answer.append(board[i][j])
    return answer

만약 이미 채워져 있는 칸에 다다른다면, 이전 칸으로 돌아간뒤 방향을 반시계방향으로 돌아 다시 진행한다.

 

n(n+1)/2 만큼의 칸채우기가 끝나면, n일때의 삼각달팽이는 완성된 것으로 보고,

 

행 = 0~n-1,열 = 0~i 순으로 board 배열의 값을 순서대로 추가한다.