No Limitation
[구현] 삼각달팽이 - 공부용 본문
https://school.programmers.co.kr/learn/courses/30/lessons/68645
이전에 풀었던 문제였는데, 다시 복습 차 시도
다시 풀어도 어려운 문제다.. 단순히 indexing으로 시도해보려고 했지만, 틀린 문제도 있었고 뒤에 유형에서는 시간초과가 발생.
처음 시도한 코드
def solution(n):
triangle = [ [0]*i for i in range(1,n+1)]
k = 0
triangle[0][0] = 1
cum = 2
### 외곽 먼저 처리
for i in range(1,n) :
triangle[i][0] = cum
cum += 1
for j in range(1,n-1) :
triangle[n-1][j] = cum
cum += 1
for h in range(n-1, 0, -1) :
triangle[h][h] = cum
cum += 1
k = 1
while True :
mul = 1
for a in range(len(triangle)) :
for b in range(len(triangle[a])) :
mul *= triangle[a][b]
if mul != 0 :
break
for i in range(k+1,n-k) :
if triangle[i][k] == 0 :
triangle[i][k] = cum
cum += 1
for j in range(k+1,n-k-1) :
if triangle[n-k-1][j] == 0 :
triangle[n-k-1][j] = cum
cum += 1
for h in range(n-k-1,k,-1) :
if triangle[h-k][h-k-1] == 0 :
triangle[h-k][h-k-1] = cum
cum += 1
k += 1
answer = []
for a in range(len(triangle)) :
for b in range(len(triangle[a])) :
answer.append(triangle[a][b])
return answer
어렵기도 하고..ㅠ 유명한 예제인거 같아서 공부하는 겸 다른 사람들의 코드를 참고!
아래 이 분이 너무 인사이트도 좋고 깔끔하게 구현하셔서 이분 코드를 공부하기로...!
https://developnote.tistory.com/26
보니까 세 번의 루트 (아래쪽으로, 우측으로, 위쪽으로)가 존재하기 때문에 이에 따른 i % 3 == 0인지, 1인지, 2인지에 따라 indexing 컨트롤을 하셨다. 코드가 예술이기도 하고 공부할 가치가 있는 코드!
def solution(n) :
### 빈 그릇을 만듬
answer = [[0 for j in range(1,i+1)] for i in range(1,n+1)]
x, y = -1, 0
num = 1
### i는 세 가지 루트 (아래, 위, 오른쪽) 중 어느 것을 정하는 지를 판별하는 기준
for i in range(n) :
for j in range(i,n) :
### 아래 방향
if i % 3 == 0 :
x += 1
### 오른쪽 방향
elif i % 3 == 1 :
y += 1
### 위쪽 방향 (삼각형이기 때문에 x, y 동시에 indexing 감소)
else :
x -= 1
y -= 1
answer[x][y] = num
num += 1
return sum(answer,[]) ## 이것도 이렇게 summation을 하는 기술이 있는 지 처음 앎... 예술 코드다..
print(solution(6))
공부할 게 태산이구만... 그래도 포기하지 말자!
'프로그래밍' 카테고리의 다른 글
[완전탐색-Union Find] 전력망 둘로 나누기 (0) | 2024.04.02 |
---|---|
[구현] A와 B (백준 12904) (0) | 2024.04.01 |
[완전탐색-DFS] 피로도 (0) | 2024.03.31 |
[최대 힙 기초] 이중우선순위큐 (1) | 2024.03.30 |
[BFS] 트리의 부모 노드 찾기 (0) | 2024.03.28 |