🦊 내 코드
from collections import deque as dq
import sys
n = int(sys.stdin.readline())
towers = [int(i) for i in sys.stdin.readline().split()]
ans = [0]*n
stack = dq()
for idx in range(-1, -(n+1), -1):
next = towers[idx]
if len(stack) == 0:
stack.append(next)
continue
else:
last = stack[-1]
if last>next:
stack.append(next)
continue
else:
poppedIdx = (idx+1)+n
while len(stack)>0:
last = stack[-1]
if last>next:
break
else:
if ans[poppedIdx]==0:
ans[poppedIdx] = idx+n+1
stack.pop()
poppedIdx +=1
stack.append(next)
print(*ans)towers 리스트 요소들을 뒤→앞 순서로 스택에 하나씩 추가
스택에 남아있음 = 수신을 받지 못 함
스택에서 pop됨 = 수신을 받음
요소를 추가할 때마다 스택의 top을 체크한다.
이때 추가하는 요소 > 스택 top 이면 스택 top을 pop(). 아니면 그냥 요소를 추가하고 다음 인덱스로 넘어간다.
스택이 비어 더이상 pop할 요소가 없거나, 추가하는 요소 < 스택 top 이 될 때까지 계속 pop(). 모든 pop이 끝나면 요소를 추가하고 다음 인덱스로 넘어간다.
사실 스택을 활용하는 아이디어는 금방 떠올렸는데, 답을 어떻게 저장해서 어떻게 출력할 것인지에서 한참을 헤맸다...
🐹 1트: 딕셔너리
towers 리스트를 순회하면서 {<탑 번호>:0} 딕셔너리를 생성했다.
원래는 [0]*n 리스트를 선언한 다음 탑 순서 그대로 답을 저장하면 될 거라고 생각했다. 근데 생각해보니 스택에서 pop할 때 답을 저장하게 되잖아? 지금 pop하는 그 요소가 towers에서 몇 번째 인덱스를 가지고 있었는지 알 수가 없어
그래서 인덱스 없이도 값을 저장할 수 있는 딕셔너리를 떠올렸다. 탑 높이가 모두 다르다는 조건이 명시되어 있었기 때문에 key로 사용하는데도 문제가 없었다.
이 방법엔 두 가지 문제가 있었다.
- 내가 알기로 딕셔너리는 출력 시 저장한 순서 그대로 출력된다는 보장이 없다.
- 출력할 때 for문을 돌리면서 모든 value값들을 문자열로 이어 붙여줘야 된다.
두번째 문제 때문인지 계속 시간 초과 에러가 나서 실패
🐻 2트: [0]*max(탑들의 높이) 배열
높이를 인덱스로 삼아서 해당 위치에 답을 저장하는 방식. 높이가 n인 탑의 정답을 list[n]에 저장하는 식.
"탑들의 높이는 1 이상 100,000,000 이하의 정수이다."
메모리 초과로 실패
🐭 3트: for문의 idx 활용하기
스택에 새로 추가하려는 요소를 next라고 칭하겠다.
뒤에서부터 차례로 스택에 추가하기 때문에, next와 스택의 top은 이웃 탑일 수밖에 없다.(스택 top은 새 요소가 추가되기 전까지 pop될 기회가 없으므로) 따라서 for문의 idx 즉 스택에 새로 추가하려는 요소의 인덱스+1을 하면 pop하는 요소의 인덱스를 구할 수 있다.
위 코드에서는 poppedIdx = (idx+1)+n 이렇게 해줬다.
pop을 여러 번 하는 경우 poppedIdx를 신경써서 업데이트 해줘야 한다.
poppedIdx를 기본적으로 1씩 증가시키면서 next의 오른쪽 탑들을 체크. 그 탑들이 현재 스택에 들어있는지 아닌지는 ans 리스트를 보면 알 수 있다. ans[poppedIdx]가 0이어야 해당 탑이 스택에 있다는 뜻이므로 ans[poppedIdx]==0인 경우에만 pop().
🐻❄️ 4트: 애초에 스택에 인덱스를 넣자
스택에 굳이 탑의 높이가 아닌 인덱스를 넣어줄 수도 있다.
towers 배열은 바뀌지 않고, 인덱싱은 O(1)이므로 비교할 때마다 스택에 담긴 인덱스로 towers에서 탑 높이를 조회할 수 있음.
