[Programmers] 삼각 달팽이 (Python 3)

문제 설명

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

 

제한사항

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

---

 

문제 처음 키고나서 이 비주얼을 보고.. 으악스러웠다

그러나 풀긴 잘 풀렸다.

 

다른 사람의 풀이들을 봤을 때 나와 완벽히 겹치는 로직은 없었던거 같아서..

뭔가 나름 독창적으로 푼 느낌이 들어 뿌듯한 문제였다.

 

 

삼각형 모양은 2차원 배열로 나타내기 까다로우므로, 구분구적법 막대그래프처럼 세운 형태로 리스트화했다.

그리고 내 로직에서 핵심 규칙은 아래 그림과 같다.

 

 

삼각 달팽이에 대충 손가락으로 달팽이 선을 그어보면서 확인해보면,

1. 총 만들어지는 직선+종점(위 사진에선 21)의 수가 n과 같다는걸 확인할 수 있다. 예시 사진의 경우 뿐만 아니라 모든 n에서 성립한다.

 

그리고 한 가지 더.

2. 직선마다 지나가는 숫자 또한 -1 공차의 등차수열 형태를 보인다.

 

이 두가지 로직을 핵심으로 코딩했다.

 

 

풀이

def solution(n):
    snail = [[None]*n for _ in range(n)]
    change = [(1,0),(0,1),(-1,-1)]
    num = 0
    cnt = -1
    x,y = -1,0
    
    for i in range(n, 0, -1):
        cnt = cnt + 1 if cnt < 2 else 0
        for j in range(i):
            num += 1
            dx, dy = change[cnt]
            x, y = x+dx, y+dy
            snail[x][y]=num
        
    return list(filter(None, sum(snail, [])))