less than 1 minute read

문제

접근 방법

문제를 읽고 오큰수 활용인 것을 알았다. 그리고 오른쪽에서 자기보다 작은 건물 수 개수를 세기 위해서는 자기보다 큰 빌딩 index에서 자기 index를 빼고 1까지 빼줘야하기 때문에 stack에 index를 저장하기로 하였다. 이때 자기보다 큰 빌딩이 없을 수 있다. 이런 빌딩들의 index는 stack에 계속 남게 되는데 이들의 벤치마킹이 가능한 빌딩의 수를 다 세려면 자기보다 오른쪽에 있던 빌딩 수를 다 계산하면 된다.

정답 코드


import sys

input = sys.stdin.readline
'''
오큰수와 같은 문제임을 알 수 있다.

자기보다 큰 수의 index - 자기 index - 1이 벤치마킹이 가능한 빌딩의 수이므로 index를 저장해야함

이때 끝까지 자기보다 큰 빌딩을 못 찾은 애들은 stack에 남는다.

'''

n = int(input())
total = 0
heights = [0]
for _ in range(n):
  heights.append(int(input()))

stack = []
for i in range(1,n+1):
  #자기보다 큰 빌딩 만난 애들은 그전에 만난 자기보다 작은 빌딩 개수를 결과값에 추가하고 pop
  while stack and heights[i] >= heights[stack[-1]]:
    total += (i-stack[-1]-1)
    stack.pop()
  
  stack.append(i)

#자기보다 큰 빌딩을 만나지 못한 애들은 전체에서 자기의 index 뺌
if stack:
  for s in stack:
    total += (n - s)

print(total)

You May Also Enjoy