[Python | 6198] 옥상 정원 꾸미기

https://www.acmicpc.net/problem/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이다.

 

📌 시간 제한: 1초

---

입력

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

---

출력

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

---

문제 접근

이 문제는 N개의 건물 높이가 주어졌을 때, 각 건물이 오른쪽에 있는 다른 건물 중 자신보다 낮은 건물을 몇 개 볼 수 있는지를 모두 합해 출력하는 문제다. 중요한 조건은 중간에 자신보다 높은 건물이 하나라도 있으면 그 뒤에 있는 낮은 건물도 가려져서 보이지 않는다는 점이다.

 

이러한 문제는 스택을 이용해 O(N)으로 해결할 수 있다. 왼쪽에서부터 하나씩 건물을 확인하면서, 현재 건물보다 낮거나 같은 높이의 건물은 스택에서 제거한다. 이유는 간단하다. 그런 건물들은 현재 건물이 보는 걸 가리지도 않고, 나중에 들어올 더 높은 건물에 의해 무조건 가려지기 때문이다. 따라서 의미가 없으므로 pop한다.

 

즉,

• 스택에는 현재까지 등장한 건물 중에서, 현재 건물보다 높은 건물만 남긴다.
• 스택의 길이는 곧 현재 건물이 볼 수 있는 건물 수가 된다.
• 왜냐하면, 스택에는 현재 건물보다 높은 건물만 들어가 있고, 이들은 전부 현재 건물보다 앞에 있으므로 볼 수 있기 때문이다.

이 과정을 거친 후, 스택에 남아 있는 건물들은 전부 현재 건물보다 높고, 현재 건물이 볼 수 있는 대상이 된다. 따라서 스택의 길이만큼을 정답에 더해주면 된다. 이때 중요한 점이 하나 있다. 스택에 현재 건물을 넣기 전에 len(stack)을 계산해야 한다. 그 이유는, 만약 먼저 push를 해버리면 자기 자신도 스택에 들어가고, 결국 자신이 자기 자신을 본다고 계산되기 때문이다. 조건상 건물은 자기 자신을 볼 수 없기 때문에, 반드시 result += len(stack)이 stack.append(height)보다 앞에 있어야 한다.

---

구현

N = int(input())
buildings = [int(input()) for _ in range(N)]
stack = []
result = 0

for height in buildings:
    while stack:
        if stack[-1] <= height:
            stack.pop()
        else:
            break
    result += len(stack)
    stack.append(height)

print(result)

 

‘탑(2493번)’이나 ‘오큰수(17298번)’ 문제와 함께 연습하면 좋다.