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

문제

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

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

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

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

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

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

• 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)

출력

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

  ---

접근

스택을 활용하여 이전의 빌딩들이 현재 빌딩을 볼 수 있는지 카운트하여 최종해를 구한다.

스택의 top보다 현재 빌딩이 크다면 스택에 더 큰 빌딩이 나올 때까지 스택을 pop한다. 현재 빌딩을 볼 수 없는 빌딩을 제거하는 과정이다.

스택의 top보다 현재 빌딩이 작다면 스택의 사이즈만큼 카운트한다. 이것은 스택에 담겨진 이전의 빌딩들이 현재 빌딩을 볼 수 있기 때문이다.

 

구현

- N개의 빌딩 높이를 입력받아 tower에 저장한다.

- 스택이 비어있다면 스택에 tower를 입력한다.

- 스택의 top보다 tower가 크다면 스택 내에서 tower보다 작은 빌딩을 모두 제거한다.

- 이후 최종해에 스택의 사이즈만큼 더하고 현재 tower를 스택에 push한다.

- 하지만 스택의 top보다 tower가 작다면 현재 스택에 있는 빌딩들이 tower를 볼 수 있기 때문에 사이즈만큼 최종해에 더하고 현재 tower를 스택에 push한다.

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

---

전체 코드

import sys
input = sys.stdin.readline

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