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

삼각달팽이

• 문제

• 해설

from math import sqrt

def n_to_total(n):
    # 4->10
    # 5->15
    # 6->21
    # n->n(n+1)/2
    return n*(n+1) // 2

def remains_to_edge_size(remains):
    # 1->1, 예외처리
    # 3->1
    # 6->2
    # 10->3
    # 15->4
    # 21->5
    # 28->6
    # 36->7
    # n(n+1)/2 -> n-1
    return round(((-1 + sqrt(1+8*remains))/ 2) - 1)

def edge_size_consumed(edge_size):
    return 3 * edge_size

def get_first(start_val, start_row_idx, start_col_idx, edge_size):
    return list(zip([*range(start_val, start_val + edge_size)], [*range(start_row_idx, start_row_idx + edge_size)], [start_col_idx]*(edge_size)))

def get_second(start_val, start_row_idx, start_col_idx, edge_size):
    return list(zip([*range(start_val+edge_size, start_val+2*edge_size)], [start_row_idx+edge_size] * edge_size, [*range(start_col_idx, start_col_idx + edge_size)]))

def get_third(start_val, start_row_idx, start_col_idx, edge_size):
    return list(zip([*range(start_val+2*edge_size, start_val+3*edge_size)], [*range(start_row_idx+edge_size, start_row_idx, -1)], [*range(start_col_idx+edge_size, start_col_idx, -1)]))

def solution(n):
    if n == 1:
        return [1]
    answer = [[0]*i for i in range(1, 1 + n)]
    funcs = [get_first, get_second, get_third]

    start_val = 1
    start_row_idx = 0  # increment : 2
    start_col_idx = 0  # increment : 1
    remains = n_to_total(n)
    edge_size = remains_to_edge_size(remains)    

    while (remains):
        for func in funcs:
            val_row_cols = func(start_val, start_row_idx, start_col_idx, edge_size)
            for val, row, col in val_row_cols:
                answer[row][col] = val
        consumed = edge_size_consumed(edge_size)
        start_val += consumed
        start_row_idx += 2
        start_col_idx += 1
        remains -= consumed
        edge_size = remains_to_edge_size(remains)
        if remains == 1:
            answer[start_row_idx][start_col_idx] = start_val
            remains -= 1

    answer = [x for sublist in answer for x in sublist]
    return answer

• 포인트
  • 각 삼각형을 외곽부터 layer-1, layer-2, …
  • 각 layer마다 세 개의 변으로 나눠 처리(왼쪽, 밑, 오른쪽을 first, second, third)
  • 이런 군수열방식이 아닌, 방향 개념 도입해서 풀면 더 간단할 듯