#29 [파이썬] 프로그래머스: 삼각 달팽이

<문제>

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

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

---

 

<소스코드>

def solution(n):
    answer = []
    triangle = [[0 for j in range(i+1)] for i in range(n)]

    i = -1
    j = 0
    num = 1

    for direction in range(n):
        for fill in range(direction, n):
            if direction % 3 == 0:
                i += 1
            elif direction % 3 == 1:
                j += 1
            else:
                i -= 1
                j -= 1
            triangle[i][j] = num
            num += 1

    answer = sum(triangle, [])
    return answer

---

 

<NOTE>

1. 핵심 아이디어

삼각형 시계 반대 방향으로 배열을 채워가는 형태를 보면, 방향이 꺾일 때까지 일정한 규칙으로 수를 채워간다. 따라서 같은 방향일 때를 큰 for문으로 두고, 그 안에서 1씩 증가시키면서 배열을 채우는 for문으로 틀을 잡을 수 있다. 이때 중요한 것은 방향을 결정하는 방법과 배열을 채워야 하는 개수가 점점 작아지는 것을 반영하는 방법이다. 참고로 n=5이면 방향을 꺾는 횟수도 5번이다. 

 

 

■ 방향 결정하는 방법

for direction in range(n):

 

direction이 0부터 n-1까지 n번 반복되는데, direction % 3은 0 또는 1또는 2가 된다. 삼각형의 특징을 이용하여 3으로 나누었을 때 나머지로 방향을 결정하는 아이디어이다. 아래, 오른쪽, 위 순서로 돌기 때문에 direction % 3 == 0이면 아래, direction % 3 == 1이면 오른쪽, direction % 3 == 2이면 위로 위치를 이동시킨다. 

 

 

■ 방향을 꺾을 때마다 배열을 채워야 하는 개수가 점점 작아지는 것을 반영하는 방법

for direction in range(n):
	for fill in range(i, n):

 

방향을 꺾을 때 마다, 즉 direction이 하나씩 증가할 때마다 채워야 하는 개수가 n개에서 하나씩 감소한다. 이를 이용하여 fill범위의 시작값을 i로 주고 끝값은 n으로 고정하면 n개로 시작해서 방향을 꺾을 때마다 1개씩 감소하면서 채울 수 있다.

 

 

2. 2차원 리스트를 1차원 리스트로 만들기

2차원 리스트의 모든 요소를 합쳐서 1차원 리스트로 만드는 방법은 여러가지가 있다. 그 중 3가지는 다음과 같다.

 

■ sum함수 이용

answer = sum(triangle, [])

 

■ itertools.chain의 from_iterable 이용

import itertools
answer = list(itertools.chain.from_iterable(triangle))

 

■ itertools.chain의 unpack(*)이용

import itertools
answer = list(itertools.chain(*triangle))

 

※만약 위의 방법을 기억하지 못했다면 반복문을 통해서 flatten시키면 된다.

for i in triangle:
    answer += i