[programmers] 삼각달팽이

출처

---

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

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

 

 

문제

---

정수 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]

 

 

입출력 예 설명

---

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 문제 예시와 같습니다.

 

 

풀이

---

규칙성은 발견했는데 구현을 못해 다른 사람의 풀이를 보고 해결했다.

해당 문제는 예시 그림들을 보면 규칙성을 발견할 수 있는데,

 

1) 방향 전환은 총 n번 일어난다.

n = 4인 경우를 보면, '↙' 방향으로 [1, 2, 3, 4], '→' 방향으로 [5, 6, 7], '↖' 방향으로 [8, 9],
다시 '↙' 방향으로 [10] 총 4회의 방향 전환이 이루어진다.

 

2) 방향 전환마다 채워넣어야 할 원소는 1개씩 줄어든다.

위의 예에서 볼 수 있듯 [1,2,3,4] → [5,6,7] → [8,9] → [10]
방향을 전환할 때마다 채워넣어야 할 원소는 1개씩 감소한다.

 

3) 방향의 주기성은 3이다.

'↙' , '→', '↖' 방향 순으로 같은 작업이 반복된다.

 

간편한 구현을 위해서 0으로 채워진 2차원 리스트를 생성하여

위 규칙대로 구현해주면 된다.

 

형태는 n이 4일 때, 아래와 같을 것이다.

[[1], 
 [2, 9],
 [3, 10, 8],
 [4, 5, 6, 7]]

 

 

코드

---

from itertools import chain

def solution(n):
	# 0으로 채운 2차원 리스트 생성
    graph = [[0] * (i+1) for i in range(n)]
    # 처음 진행방향은 '↙'으로 x축을 따라 내려가기 때문에 x = -1
    x, y = -1, 0
    num = 1
    
    # n번 방향 전환을 하며
    for i in range(n):
    	# i번 방향 전환을 할 때마다 n-i개의 원소를 채운다.
        for j in range(i, n):
        	# 방향 전환의 주기는 3
            # '↙' 방향일 때
            if i % 3 == 0:
                x += 1
                
            # '→' 방향일 때
            if i % 3 == 1:
                y += 1
                
            # '↖' 방향일 때
            if i % 3 == 2:
                x -= 1
                y -= 1
            graph[x][y] = num
            num += 1
            
    answer = list(chain(*graph))
    return answer