오늘의 문제 - boj-6198

boj-6198

문제

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

풀이

처음시도

볼 수 있는 정원의 수를 담는 answer를 0으로 초기화한다.

stack에 빌딩의 높이를 담아주면서 다음 높이 값과 비교해서 큰 값이 나올 때까지 순회한다.

높이값이 stack에 담긴 높이보다 높다면 stack에서 그 값을 pop해주고 지금 높이의 인덱스와 

비교값인 더 높은 빌딩의 인덱스 차이를 빼서 answer의 해당인덱스에 값을 할당한다.

변경

각 빌딩들이 얼마나 볼 수 있는지 여부는 저장할 필요가 없다.(총 값만 구하면 됨)

따라서 stack에서 일일이 인덱스를 통해서 값을 answer테이블에 넣기보다는 answer에 직접적으로 더해주면 된다.

현재 빌딩의 높이가 이전 빌딩보다 높다면 세어줄 필요가 없기 때문에 pop을 해주고 stack에 남은 값들은 현재 빌딩값보다 높기 때문에 현재까지 모든 정원들을 볼 수 있으므로 남아있는 스택값들을 answer에 더하는 것을 반복해 최종 값을 구해준다.

import sys
input = sys.stdin.readline

N = int(input().rstrip())

answer = 0
stack = []

for _ in range(N):
    building = int(input().rstrip())
    while stack and stack[-1] <= building:
        stack.pop()
        
    answer += len(stack)
    stack.append(building)
    
print(answer)