[백준/6198] 옥상 정원 꾸미기 (Python)

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

6198번: 옥상 정원 꾸미기

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:06:43

 

---

 

문제 설명

 

 

도시에는 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)

 

출력

 

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

 

입력 예시

 

6
10
3
7
4
12
2

 

출력 예시

 

5

 

 

---

 

풀이

 

각 관리인이 '오른쪽'만을 바라볼 수 있고, '자신보다 높거나 같은 빌딩이 등장하기 전까지의 빌딩들'만 바라볼 수 있으므로 우리는 스택을 한 번 사용해 봄직하다. 내림차순으로 정렬되도록 스택을 push 및 pop한다면, 그 스택 안의 각 빌딩은 '자신이 현재 바라볼 수 있는' 빌딩들로 구성됨이 항상 보장된다.

 

• 스택이 비지 않았고, 스택 마지막 빌딩의 높이보다 현재 높이가 크거나 같다면 이 조건을 만족하지 않을 때까지 스택을 pop한다. 이 때, pop한 (각 원소의 idx와 현재 idx의 차 - 1)가 그 원소가 바라볼 수 있는 건물의 개수가 된다. 
• 위 반복문의 조건을 만족하지 않을 때 현재 빌딩의 인덱스와 높이를 스택에 push한다.
• 모든 빌딩에 대해 이를 시행하며, 마지막에 스택이 남았을 경우 1번의 반복문을 스택이 빌 때까지 pop하도록 한다.

 

 

풀이 코드

import sys
input = sys.stdin.readline
N = int(input())
ans = 0
stk = list()
for i in range(N) :
  h = int(input())
  while stk and stk[-1][0] <= h :
    _h, idx = stk.pop()
    ans += i-idx
  stk.append((h, i))
while stk :
  _, idx = stk.pop()
  ans += N-idx
print(ans-N)

풀이 완료~