(Python/LV2) 삼각 달팽이

문제출처: https://school.programmers.co.kr/learn/courses/30/lessons/68645

프로그래머스

풀이:

def solution(n):
    tri = [[0 for i in range(1, n+1)] for i in range(1, n+1)]
    num = 1
    x,y =-1, 0
    for i in range(n):
        for j in range(i, n):
            if i % 3 == 0: # 아래
                x += 1
            elif i % 3 == 1: # 오른쪽
                y += 1
            elif i % 3 == 2: # 위쪽 대각선
                x -= 1
                y -= 1
            tri[x][y] = num
            num += 1
    tri = sum(tri, [])
    while 0 in tri:
        tri.remove(0)
    return tri
# 시간 초과

정답풀이:

def solution(n):
    tri = [[0 for i in range(1, n+1)] for i in range(1, n+1)]
    num = 1
    x,y =-1, 0
    for i in range(n):
        for j in range(i, n):
            if i % 3 == 0: # 아래
                x += 1
            elif i % 3 == 1: # 오른쪽
                y += 1
            elif i % 3 == 2: # 위쪽 대각선
                x -= 1
                y -= 1
            tri[x][y] = num
            num += 1
    res = []
    for i in tri:
        for j in i:
            if j != 0:
                res.append(j)
    return res
# 아래 while 문 for 이중 포문으로 바꿈

 

delete 자체가 앞에서부터 검색해서 지우므로 시간복잡도가 엄청나다