[백준 6198] 옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

from collections import deque

n = int(input()) # 빌딩 개수 
buildings = deque() # 각 빌딩을 왼쪽부터 층수 입력받는 리스트 
stack = deque() # 스택 
result = 0 # result

# 각 빌딩의 층수 입력 
for _ in range(n):
    buildings.append(int(input()))

# 각 빌딩마다 처리 
# 볼 수 있는 건물의 수를 세는 것이 아닌 (다른 건물에게) 보여지는 횟수를 세는게 핵심 
for building in buildings:
    # 각 빌딩마다 스택에 쌓다가 자기보다 작은 스택 요소가 나오면 빼서 (다른 건물에) 보여지는 횟수를 체크 
    while stack and stack[-1] <= building:
        stack.pop()
    result += len(stack) # 스택 개수 == 보여지는 건물수
    stack.append(building) # 현재 위치의 건물을 스택에 추가
print(result)

stack.append(building) 코드를 통해 모든 건물은 한번은 스택에 쌓이게 되므로, 

스택에 있는 요소들중에 제일 위에 있는 건물 (현재 건물의 바로 왼쪽에 있는 건물)부터 차례로 왼쪽으로 비교해가면서 자기보다 작으면 보여지지 않으므로 빼고, 자기보다 크면 그 왼쪽의 건물들에게는 보여지므로 남겨둔다. 

 

그리고 위의 과정을 그 전에도 계속 했었다면 스택에는 내림차순으로 건물들이 쌓이면서 자기보다 큰 건물을 만난 시점 이후로는 계속 자기보다 큰 건물들만 쌓여있으므로 while 문을 종료한다. 

 

그런 다음 남아있는 스택 개수는 현재 위치의 건물을 볼 수 있는 건물 수 이므로 결과를 추가하고 현재 위치의 건물을 스택에 쌓는다.