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

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

6198번: 옥상 정원 꾸미기

문제

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

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

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

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

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

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

출력

• 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

문제 풀이

• 자주 봤던 유형의 문제라 접근이 쉬웠다!
• 각 빌딩의 관리인이 오른쪽에 위치한 빌딩들만 확인할 수 있으므로, 맨 오른쪽부터 빌딩부터 for문을 이용해서 접근했다.
• 처음에 맨 오른쪽 빌딩의 높이와 번호를 스택에 넣어둔다.
• 그리고 바로 왼쪽 빌딩부터 for문을 이용해서 탐색을 시작한다.
• stack의 top에 위치한 빌딩이 자신보다 더 높은 빌딩이 될 때까지 stack을 pop하고 pop한 개수를 세어준다. 
• 그리고 만약 pop한 빌딩 중 해당 빌딩에서 볼 수 있는 빌딩의 개수를 저장해놓은 배열 ans의 값이 0보다 클 경우 현재 빌딩에서도 확인할 수 있지만, 이전 계산 과정에서 pop된 빌딩이 존재한다는 의미이므로 해당 빌딩의 ans 값을 pop_number에 추가로 더해준다. 
• 그리고 자신보다 작은 건물을 모두 pop한 뒤엔 현재 빌딩의 높이와 번호를 스택에 추가해준다. 
• 이러한 과정을 거쳐 ans에 저장된 각 빌딩에서 볼 수 있는 빌딩의 개수를 모두 더해서 출력해주면 된다. 

import sys
from collections import deque

n=int(sys.stdin.readline())
buildings=[int(sys.stdin.readline()) for _ in range(n)]

# 각 관리인이 볼 수 있는 빌딩의 개수
ans=[0]*n

stack=deque()
stack.append((buildings[-1], n-1))
for i in range(n-2,-1,-1):
    # stack의 top부터 시작해서 현재 빌딩의 위치보다 작은 빌딩 pop하고 ans 배열에 pop된 개수만큼 추가
    # ans 배열에 해당 빌딩의 번호에서 볼 수 있었지만, 해당 빌딩보다 작아서 pop된 개수도 추가해줌
    pop_number=0
    while stack and stack[-1][0]<buildings[i]:
        height, num=stack.pop()
        if ans[num]>0:
            pop_number+=ans[num]
        pop_number+=1
    ans[i]=pop_number
    # 자신보다 작은 건물 모두 pop한 뒤에 자신 추가
    stack.append((buildings[i], i))

print(sum(ans))