No Limitation
[구현] 삼각 달팽이 - 프로그래머스 본문
https://programmers.co.kr/learn/courses/30/lessons/68645
전에 월간 코드 챌린지를 참여했을 땐 시간 부족으로 풀지 못했던 문제인데
기회가 생겨 다시 풀게 되었다.
당시는 규칙을 찾으려고 발버둥을 쳤던 문제였는데 단순 구현 문제였다.
논리는 단순하다.
우선 다음과 같이 0을 담고 있는 빈 삼각형을 만들어준다.
다음으로
[1] 첫 번째 요소를 채워주는 반복문을 구축한다.
[2] 다음으로 마지막 element요소를 채워주는 반복문을 구축한다.
마지막 element를 채운 뒤에는 마지막 요소를 제거한다.
[3] 끝 열 중 0이 아닌 부분을 채운다.
[4] 다음 단계로 넘어가면서 마찬가지의 단계를 수행해준다. idx를 통해 control 한다.
총 0이 없을 때까지 수행한다.
이러한 논리를 구현하는 코드를 작성하였는데 다만 복잡도가 꽤 커서 시간 복잡도가 걸릴지 걱정이었지만 다행히 통과하였다.
def solution(n):
triangle = []
for i in range(1,n+1) :
triangle.append([0]*i)
## 프로그램 시작
idx = 0
level = 0
accum = 0
total_result = []; flag = False
def find_index(ls) :
result = 0
for i in range(len(ls)-1, -1, -1) :
if ls[i] == 0 :
result = i
break
return result
while True :
## 초반 거 채우기
for i in range(idx, len(triangle)) :
if triangle[i][idx] == 0 :
flag = True
accum += 1
triangle[i][idx] = accum
if not flag :
break
## 마지막 행 채우기
for j in range(idx+1, len(triangle)) :
if triangle[len(triangle)-1][j] == 0 :
accum += 1
triangle[len(triangle)-1][j] = accum
## 끝에 거 채우기
total_result.append(triangle.pop())
for k in range(len(triangle)-1, -1, -1) :
ii = find_index(triangle[k])
if triangle[k][ii] == 0 :
accum += 1
triangle[k][ii] = accum
idx += 1
flag = False
for _ in range(len(triangle)) :
total_result.append(triangle.pop())
Final_result = []
for ele in range(len(total_result)-1, -1, -1) :
Final_result.extend(total_result[ele])
return Final_result
'프로그래밍' 카테고리의 다른 글
[DP] 1, 2, 3 더하기 4 - 백준 (0) | 2022.02.04 |
---|---|
[DP] 퇴사2 - 백준 (0) | 2022.02.04 |
[Greedy] 동전0 - 백준 (0) | 2022.02.03 |
[DP] 평범한 배낭 - 백준 (0) | 2022.02.03 |
[DP] 설탕 배달 - 백준 (0) | 2022.02.02 |