[백준/파이썬(Python)] 옥상정원꾸미기 Gold5 6198

💌문제

---

https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

💌풀이

---

와 마지막에 스택에 남았을 때… 저거 처리하는거 때메 시간 꽤 썼다.

뒤에 있는 수 중에서 가장 큰 수를 구하는 방법으로(스택이용)

큰 수를 구하면 일단 answer에 그 값을 넣고, count에 그 큰 수가 있는 인덱스-현재 나의 인덱스값을 넣어서 볼 수 있는 빌딩 갯수를 구한다.

스택에 값이 남아있으면 그것도 처리해줘야 해서, 즉, 더 큰 수를 만나지 못한 빌딩은 남아있는 다른 빌딩을 다 볼 수 있기 때문에 마지막 인덱스 값인 n에서 스택에서 꺼낸 인덱스 값을 빼줘야 한다.

 

💌파이썬 코드

---

import sys
input=sys.stdin.readline
n=int(input())
num=[]
for i in range(n):
    num.append(int(input()))

num.append(sys.maxsize)
cnt=[0]*(n+1)
st=[]
for i in range(n):
    while len(st)!=0 and (num[st[-1]]<=num[i]):
        idx=st.pop()
        cnt[idx]=i-idx-1
    st.append(i)
while st:
    idx=st.pop()
    cnt[idx]=(n-1)-idx
print(sum(cnt))