백준 #2493

백준 2493번: 탑

🦊 내 코드

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에서 탑 높이를 조회할 수 있음.