삼각달팽이

문제설명

문제 설명

정수 n이 매개변수로 주어집니다.
다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 1 이상 1,000 이하입니다.

입출력 예

n	result
4	[1,2,9,3,10,8,4,5,6,7]
5	[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6	[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

작성코드

def solution(n):
    answer = []
    snail=[[0 for j in range(i)]for i in range(1,n+1)]
    temp=[1,2,3,4]
    print(all(temp))
    left,right=True,False
    leftindex,height,index,reverse=0,0,0,-1
    n_max=n-1
    final_num=sum([i for i in range(1,n+1)])
    for num in range(1,final_num+1):
        if left:
            snail[height][leftindex]=num
            if height==n_max:
                left=False
                index=leftindex+1
            else:
                height+=1
        elif right:
            snail[height][reverse]=num
            if all(snail[height]):
                left,right=True,False
                height+=1
                reverse-=1
                leftindex+=1
            else:
                height-=1
        else:
            snail[height][index]=num
            if all(snail[height]):
                right=True
                height-=1
                n_max-=1
            else:
                index+=1
    for i in snail:
        answer+=i
    return answer

개인적인 풀이

참 재미있는 문제였다.
최근에 알고리즘 수업에서 배운 direction 문제인것 같았다.
이 삼각형을 채울때는 방향이 단 3개만 존재한다.

1. 좌하단으로 내려가기
2. 오른쪽으로 가기
3. 좌상단으로 올라가기

이 세가지가 존재한다.
나는 이것을 left, right로 정의하였고, 1번과 3번은 left, 2번은 right였다.
또한 다중리스트로 만들어서 깊이가 존재했기때문에, 이를 순회하기 위한 것들을 만들었다.
leftindex는 1번이 행해질때마다 1개씩 늘어난다.
그림에서도 보면 1번이 실행될때는 항상 0번..1번..이렇게 변한다. 그리고 값을 채울 자리가 다른 값으로 채워져 있을 경우 2번을 수행한다.

그리고, 2번이 이루어질때는 항상 그 줄의 index를 벗어날 때 까지 값들을 채워나가면 된다.

마지막 3번이 이루어 질때는, python에서 제공하는 리스트의 -1, -2인덱스들을 사용해서 1번과 유사하게 채워나가나, 채울 자리가 이미 다른 값으로 채워져 있다면 다시 1번을 실행한다.

이를 1부터 n까지를 모두 더한숫자 n*(1+n)/2 만큼 loop를 돌면 딱 끝난다.