2023년 10월 13일 알고리즘 문제풀이
문제 1 삼각달팽이
1차 시도
나의 생각
처음에는 각 삼각형의 높이마다 배열을 만들어주고 해당 높이에 append로 추가해주면 되겠다 생각했다. 하지만 정답을 출력할 때 순서대로 출력해야하다보니 각 배열 안에서의 순서가 지켜지지 않게 되는 것을 깨달았다. 따라서 각 행의 길이를 직접 정해주었다. i번째 행은 길이가 i가 되도록 배열을 만들었다.
삼각형 한 바퀴를 도는 것을 기준으로 함수를 만들었다. 함수의 인수 cnt는 넣을 숫자, l은 이번에 돌 삼각형의 한 변의 길이, idx는 출발이 몇번째 행인지를 나타내고, depth는 함수가 실행된 횟수이자 지금 도는 삼각형이 내부에서 얼마나 깊이 있는지를 의미한다.
맨 처음 한바퀴는 가장 밖을 돌게 된다. 그다음은 한 칸 안에있는, 한 변의 길이가 3만큼 줄어든 삼각형을 돌게된다. 따라서 l은 3이 감소한다. 이때는 처음과 달리 첫 시작지점이 2번째 행에 있게되어서 idx 를 2 더해주었고 가장 밖이 아니라 한 칸 내부에 입력되야하기 떄문에 depth 도 1을 더해주었다. 입력해야할 값을 return하도록 해서 다음 입력을 시작하는 수를 표시할 수 있도록 해주었다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def solution(n):
arr = []
for i in range(n):
arr.append([0 for _ in range(i+1)])
def snail(cnt,l,idx,depth):
if l == 1:
arr[idx][depth] = cnt
return
for _ in range(l-1):
arr[idx][depth] = cnt
cnt += 1
idx += 1
for k in range(l-1):
arr[idx][k+depth] = cnt
cnt += 1
for _ in range(l-1):
max_idx = len(arr[idx])-1
arr[idx][max_idx-depth] = cnt
cnt += 1
idx -= 1
return cnt
cnt = 1
l = n
idx = 0
depth = 0
while l > 0:
tmp = snail(cnt,l,idx,depth)
cnt = tmp
l -= 3
idx += 2
depth += 1
answer = []
for i in range(n):
for x in arr[i]:
answer.append(x)
return answer
