[Level 2] 삼각 달팽이

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

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

---

접근

이 문제처럼 어떠한 규칙에 의해 수들이 정렬되어 있을 때 방향이 어떠한 규칙으로 반복되는지, 인덱스는 어떻게 변하는지 등을 생각해볼 필요가 있다.

이 문제는 아래, 오른쪽, 위 방향이 반복되어지고 있다. 그리고 방향이 바뀔 때마다 포함된 숫자들이 하나씩 감소하고 있다. 이 부분을 신경써서 구현을 해보자.

 

구현

NxN 크기의 그래프를 생성하여 0으로 초기화하였다. 이 그래프에 숫자들을 채워나간다.

처음에 y는 -1로 시작하는데 이는 첫 번째 방향이 아래로 향하는 것이고 -1다음 0행에 수를 채우기 위함이다.

그리고 수는 number=1부터 시작한다.

 

첫 번째 for문은 방향이 바뀌는 것이 총 n번 진행된다. 그리고 각 방향이 바뀔 때마다 숫자들이 n개에서 1씩 감소를 하기 때문에 두 번째 for문에서 이를 정해준다. 즉 n까지의 범위를 하나씩 좁혀가면서 각 방향에 정렬된 수의 개수를 감소시킨다.

방향이 바뀌는 규칙을 보면 아래, 오른쪽, 위이고 3방향이 반복된다. 따라서 0, 1, 2일 때 어떤 위치에 숫자를 채울 것인지 정한다. i를 3으로 나눴을 때 나머지가 각각 0, 1, 2에 따라 방향을 정해주도록한다.

 

위 과정을 거쳐 그래프가 완성이 되었을 때 2중 for문으로 그래프 내에 0보다 큰 수들을 answer에 추가한다.

def solution(n):
    answer = []
    graph = [[0 for _ in range(n)] for _ in range(n)]
    y, x = -1, 0
    number = 1
    for i in range(n):
        for j in range(i, n):
            if i%3 == 0:
                y += 1
            elif i%3 == 1:
                x += 1
            elif i%3 == 2:
                y -= 1
                x -= 1
            graph[y][x] = number
            number += 1
    for y in range(n):
        for x in range(n):
            if graph[y][x] > 0:
                answer.append(graph[y][x])
    return answer