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

 

 

문제 링크

 

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

6198번: 옥상 정원 꾸미기

 

 

문제 풀이

 

단순히 빌딩 하나씩을 확인하며 더 낮고 오른쪽에 있는 빌딩들을 찾을 수도 있지만 시간 초과의 문제가 발생합니다.

문제의 해결 방안은 반대로 현재 기준의 빌딩이 보여질 수 있는 왼쪽의 높은 빌딩들을 찾아나가는 것입니다.

 

for b in buildings:
  while stack and stack[-1] <= b:
    stack.pop()
  stack.append(b)
  result += len(stack) - 1

 

stack에 0번 빌딩의 높이부터 순차적으로 추가하고,

만약 이미 stack에 들어있는 높이 중 현재 높이보다 작은 것이 있다면 모두 pop을 시켜줍니다.

현재 빌딩이 보여질 수 있는 더 높은 빌딩들을 찾고 있는 것이기 때문입니다.

그리고 남은 빌딩의 수를 result에 더해주는 과정을 모든 빌딩에 대해서 해주면 됩니다.

현재 높이를 기준으로 작은 왼쪽의 빌딩들을 pop하기 때문에,

이전에 pop한 높이보다 작은 빌딩의 경우 원하는 높은 빌딩을 모두 구할 수 없지 않느냐는 생각이 들 수 있지만

삭제된 빌딩들은 이미 대조되었던 높은 빌딩에 가려 그 이후에 있는 빌딩들을 볼 수 없습니다.

 

전체 코드

 

n = int(input())
buildings = []
for i in range(n):
    buildings.append(int(input()))

stack = []
result = 0

for b in buildings:
  while stack and stack[-1] <= b:
    stack.pop()
  stack.append(b)
  result += len(stack) - 1

print(result)