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

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

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

 

전에 월간 코드 챌린지를 참여했을 땐 시간 부족으로 풀지 못했던 문제인데

기회가 생겨 다시 풀게 되었다. 

 

당시는 규칙을 찾으려고 발버둥을 쳤던 문제였는데 단순 구현 문제였다. 

 

논리는 단순하다.

 

우선 다음과 같이 0을 담고 있는 빈 삼각형을 만들어준다.

다음으로 

[1] 첫 번째 요소를 채워주는 반복문을 구축한다.

[2] 다음으로 마지막 element요소를 채워주는 반복문을 구축한다.

마지막 element를 채운 뒤에는 마지막 요소를 제거한다. 

 

[3] 끝 열 중 0이 아닌 부분을 채운다. 

[4] 다음 단계로 넘어가면서 마찬가지의 단계를 수행해준다. idx를 통해 control 한다. 

 

총 0이 없을 때까지 수행한다. 

 

이러한 논리를 구현하는 코드를 작성하였는데 다만 복잡도가 꽤 커서 시간 복잡도가 걸릴지 걱정이었지만 다행히 통과하였다. 

 

def solution(n):
    triangle = []
    for i in range(1,n+1) :
        triangle.append([0]*i)

    ## 프로그램 시작
    idx = 0
    level = 0
    accum = 0
    total_result = []; flag = False

    def find_index(ls) :
        result = 0
        for i in range(len(ls)-1, -1, -1) :
            if ls[i] == 0 :
                result = i
                break
        return result
    while True :
        ## 초반 거 채우기
        for i in range(idx, len(triangle)) :
            if triangle[i][idx] == 0 :
                flag = True
                accum += 1
                triangle[i][idx] = accum
        if not flag :
            break
        ## 마지막 행 채우기
        for j in range(idx+1, len(triangle)) :
            if triangle[len(triangle)-1][j] == 0 :
                accum += 1
                triangle[len(triangle)-1][j] = accum
        ## 끝에 거 채우기
        total_result.append(triangle.pop())
        for k in range(len(triangle)-1, -1, -1) :
            ii = find_index(triangle[k])
            if triangle[k][ii] == 0 :
                accum += 1
                triangle[k][ii] = accum

        idx += 1
        flag = False

    for _ in range(len(triangle)) :
        total_result.append(triangle.pop())

    Final_result = []
    for ele in range(len(total_result)-1, -1, -1) :
        Final_result.extend(total_result[ele])
    return Final_result