알고리즘 코드카타 108 - 삼각 달팽이

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

프로그래머스

 

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

예시

제한사항
n은 1 이상 1,000 이하입니다.

 

삼각형모양으로 수를 배치한 후 만들어진 모양을 리스트로 반환하는 알고리즘, 다행히 n의 범위가 100까지이기 때문에 시간복잡도 문제에서 상대적으로 자유로울것같다.

 

triangle = [[0] * i for i in range(1, n + 1)]
    
    num = 1
    x = 0
    y = 0

입력값 〉	4
출력 〉	[[0], [0, 0], [0, 0, 0], [0, 0, 0, 0]]

 

먼저 삼각형 모양의 2차원 리스트를 만들어준다.

 

for i in range(n):
        for _ in range(n-i):
            if i % 3 == 0:
                x += 1
            elif i % 3 == 1:
                y += 1
            elif i % 3 == 2:
                x -= 1
                y -= 1
            triangle[x][y] = num
            num += 1

주어진 조건에 따라 리스트를 순회하면서 숫자를 추가해준다. 내가 스스로 떠올린 것은 아니고 검색의 도움을 많이 빌렸다.

첫번째 반복문은 숫자를 입력해나갈 방향을 결정한다. i의 값에 따라 순서대로 다음 층으로 이동, 층내에서 가로로이동, 위층의 왼쪽으로 이동을 반복하면서 삼각형으로 이동한다.

두번째 반복문은 숫자의 입력횟수를 결정한다. 최초에는 당연히 n만큼 입력을 하지만 방향을 바꿀때마다 i값이 증가함에 따라 입력횟수가 감소해서 삼각형모양으로 이동을 한다.

 

answer = []
    for row in triangle:
        answer.extend(row)

 

마지막으로 리스트를 1차원으로 변환해서 출력하면 된다.

 

통과?

 

문제를 풀긴했지만 아직 잘 모르겠는 점이 많다. 핵심적인 부분은 대부분 검색으로 해결했기 때문이기도 하지만 이 알고리즘을 내가 어떻게 떠올릴 수 있을지 잘 모르겠다.

그래도 접근법 자체는 근접했..나? 리스트의 모양을 직각삼각형 모양으로 떠올리는 것까지는 가능했다. 그 안에서 숫자의 입력방향과 횟수를 결정하는 부분은 실패해버렸지만...

 

예전에 풀었던 행렬자르기문제도 그렇고 공간적인 아이디어를 떠올리는 것이 참 힘든것같다.