Skip to main content

2493 - 탑

info
  • 문제 보기: 2493 - 탑
  • 소요 시간: 34분 31초
  • 풀이 언어: python
  • 체감 난이도: 2️⃣~3️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

자료구조 스택


풀이 코드​

info
  • 메모리: 115756 KB
  • 시간: 472 ms
import sys
input = sys.stdin.readline

def solution():
    n = int(input())
    tower = list(map(int, input().split()))
    st = [] # stack
    
    ans = [0] * n
    for idx in range(1, n+1): # tower # starts from 1
        
        while st:
            top = st[-1]
            if top[1] > tower[idx-1]: # top() height > tower[idx] height
                ans[idx-1] = top[0] # top() receives tower[idx] signal
                break
            else:
                st.pop() # update top()
                
        st.append((idx, tower[idx-1])) # tower(idx, height)
        
    print(*ans)


if __name__ == '__main__':
    solution()

풀이 해설​

다이어그램

📌중간에 가장 높은 tower가 있는 경우​

→ 계속 stack을 pop() 하다가 결국 stack이 empty하게 됨
→ 다시 for문으로 돌아와 다음 기준이 되는 tower를 stack에 push()


메모​

  • 발상이 어렵고 구현은 쉬운 문제