[파이썬][백준 2493][스택] 탑 - 컴도리돌이

---

2493번: 탑

---

풀이 과정

 

아마도 스택 문제에서 괄호 문제 다음으로 많이 나오는 스택 문제 유형인 거 같다. 해당 유형을 처음 접하시는 분들은 일단은 머릿속에 배열의 순서를 생각하면서 카피하시면 왜 스택으로 사용하는지 이해가 갈 것이다. (아님 말고~)

 

1. 스택처럼 사용할 q라는 배열 안에 입력받은 값의 마지막 값과 인덱스를 각각 넣어준다. 그리고 출력할 answer도 따로 입력받은 n의 크기만큼 할당해준다.

 

2. n-2 번째 인덱스부터 첫 번째 인덱스까지 검사를 시작한다.

 

3. 스택의 top의 값과 현재 인덱스의 값과 비교해서 작을 경우 -> 스택이 비어있지 않고 top값이 현재 값보다 작을 경우 while문으로 pop을 시키면서 top 값의 인덱스에 해당한 값들을 현재 인덱스 값을 넣어준다.

 

4. 큰 경우에는 스택에 넣어준다.

---

풀이 코드

import sys; input = sys.stdin.readline
n = int(input()) ; arr = list(map(int,input().split())) ; q = [[n-1,arr[-1]]] ; answer = [0] * (n)

for i in range(n-2,-1,-1) :
  if  q[-1][1] < arr[i]: 
    while q and q[-1][1] < arr[i] :
      answer[q.pop()[0]] = i+1
    q.append([i,arr[i]])
  else :
    q.append([i,arr[i]])

for a in answer :
  print(a,end = " ")