Programmers. 삼각 달팽이

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 삼각 달팽이

문제 풀이

뭔가 겁나 우아한 알고리즘이 있을 줄 알았는데 그냥 삼각형의 각 행의 길이가 $1,2,3,\dots$식으로 증가하고 각 방향으로 움직이는 수도 n-1, n-2, ...로 줄어든다는 규칙을 참고해 2차원 배열을 선언한 뒤 좌표를 이동시켜서 구현하는 문제였다. 난이도가 쉬워서 너무 짧은 풀이만 고려한 게 패착이었다.

• 원소를 입력할 직각 삼각형 형태의 2차원 배열을 생성한다.
• 커서를 이동시킬 방향을 설정한다. 아래, 오른쪽, 좌상향 대각선 방향이다.
• n부터 1까지의 값만큼 이동하되 방향을 정해서 2차월 배열의 값을 갱신한다.
• 마지막까지 순회를 완료하면 2차원 배열의 원소를 하나의 배열에 저장해 리턴한다.

python 코드

def solution(n):
    board = []
    for i in range(1, n + 1):
        board.append([0] * i)
    direc = [(1, 0), (0, 1), (-1, -1)]
    c = [-1, 0]
    d = 0
    s = 0
    for i in range(n, 0, -1):
        for _ in range(i):
            c[0] += direc[d % 3][0]
            c[1] += direc[d % 3][1]
            s += 1
            board[c[0]][c[1]] = s
        d += 1
    answer = []
    for b in board:
        for x in b:
            answer.append(x)
    return answer