[Programmers/ level2] 삼각 달팽이
👩문제
정수 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이고 한 변의 길이가 7이므로 마지막 수는 1+7+6+5-1= 15이다.
- 첫 수와 마지막 수를 안다면 우리는 다음 세과정을 통해서 삼각형 테두리의 숫자들을 구할 수 있다.
- 꼭대기 층에는 첫 수가 들어간다.
- 2-마지막 전층까지는 첫 수에서 1씩 증가한 수, 마지막 수에서 1씩 감소한 수가 들어가게 된다.
- 마지막 층에서는 나머지 숫자들이 차례로 들어가게 된다.
- 위의 과정을 변의 길이가 0이 될 때까지 단계적으로 진행한다.
- 각 층의 리스트는 각 단계에서의 앞 수가 저장될 리스트와 뒷 수가 저장될 리스트, 2개의 리스트가 존재한다.
그렇다면 이제 코드를 통해 조금 더 자세히 살펴보자!
from collections import deque
def getAnswer(n, num, str, end):
e = num+n*3-4
answer[str][0].append(num) #꼭대기층
num += 1
for i in range(str+1, end): #2-마지막 전층
answer[i][0].append(num)
num += 1
answer[i][1].appendleft(e)
e -= 1
for i in range(num, e+1): #마지막층
answer[end][0].append(i)
def solution(n):
global answer
answer = [[deque(), deque()] for i in range(n)]
num = 1
str, end = 0, n-1
for i in range(n, 0, -3): #각 단계에서 변의 길이는 3씩 줄어든다.
getAnswer(i, num, str, end)
num += i*3-3
str += 2
end -= 1
result = []
for i in range(n):
tmp = list(answer[i][0])+list(answer[i][1])
result += tmp
return result
🔔best 풀이
해당 문제에서의 best 풀이라고 생각되는 코드를 가져와봤다!!
그렇다면 그 접근방식은 어떨까??
☝️ 우선 우리는 n을 알면 마지막 수를 알 수 있다.
- n=6일 때 마지막 수는 6+5+4+3+2+1= 21이 된다.
- 즉 n*(n+1)//2가 되는 것이다.(1부터 n까지의 합공식)
✌️ 두 번째로 살펴볼 것은 숫자들이 어떻게 채워지는 지이다.
- 숫자의 흐름은 다음과 같이 크게 세단계로 달라진다.
- 각 단계마다 x와 y의 값은 그림에서와 같이 증가하고 감소한다.
👌 코드 작성!
def solution(n):
dx=[0,1,-1];dy=[1,0,-1] #숫자의 흐름이 바뀌는 세단계
graph=[[0]*i for i in range(1,n+1)]
x,y=0,0;num=1;d=0
while num<=(n+1)*n//2:
graph[y][x]=num
ny=y+dy[d];nx=x+dx[d];num+=1
if 0<=ny<n and 0<=nx<=ny and graph[ny][nx]==0:y,x=ny,nx
else:d=(d+1)%3;y+=dy[d];x+=dx[d]
return sum(graph,[])
🤗 아마 위의 풀이를 이해했다면 코드는 쉽게 이해할 수 있을 것이다!!
여기서 또 짚어볼 만한 코드는 바로 🔔sum(graph, [])이다!!
- 여기서는 각 리스트의 값을 모두 합쳐 하나의 리스트로 결과를 반환해야 한다.
- sum(iterable, start) 사용!
- sum(iterable)의 경우 default로 start에 0이 들어가는 경우이다.
- sum(graph, [])의 경우에는 []인 빈리스트로 시작하여 graph의 각 리스트들을 하나씩 합치게 된다.
정말 간편하고 쉬운 방법인 것 같다!!(오늘도 배웠다😳)
👩💻배운 점
- sum(iterable(요소가 리스트인 경우), [])를 통해서 중첩리스트를 하나의 리스트로 변환할 수 있다.
🙇♀️풀이에 부족한 부분이 있다면 말씀해주세요! 감사합니다!
댓글남기기