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

1. 문제

6198번: 옥상 정원 꾸미기

2. 개요

N개의 빌딩이 있다.

빌딩마다 관리인이 있으며 관리인은 자신의 빌딩에서 오른쪽으로만 볼 수 있다.

그리고 자신의 빌딩보다 낮은 빌딩의 옥상만을 볼 수 있다.

이때 관리인들이 볼 수 있는 다른 모든 빌딩들의 옥상의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

스택을 이용한다.

왼쪽 빌딩의 번호부터 스택에 넣어간다.

만약 현재 탐색하는 빌딩의 높이가 스택의 마지막 빌딩의 높이보다 크다면, 이보다 더 작은 빌딩들은 더이상 옥상을 볼 수 없다는 의미가 된다.

더 큰 높이의 빌딩이 나올 때까지 스택을 Pop해준다.

이때 탐색은 빌딩 번호로 진행했으므로 현재 탐색하는 빌딩 - Pop한 번호 -1 이 Pop한 번호의 빌딩이 볼 수 있는 옥상의 수가 된다. 이를 answer에 더해준다.

위 작업을 마치고 스택에 남은 것들을 처리한다.

스택에 남아있는 것들은 해당 위치에서 자신보다 높은 빌딩이 없었기 때문에 남아있게 된 것이다.

따라서 자신보다 오른쪽에 있는 모든 건물들의 옥상을 볼 수가 있다.

그렇기 때문에 스택을 비울때까지 Pop하며 빌딩 전체 수 - Pop한 번호 -1 을 answer에 더해준다.

3-2. Python

import sys

N = int(sys.stdin.readline())

buildings = []
stk = []
answer = 0
for i in range(N):
    buildings.append(int(sys.stdin.readline()))

for i in range(N):
    while stk and buildings[stk[-1]] <= buildings[i]:
        answer += i - stk.pop() -1
    stk.append(i)

while stk:
    answer += N - stk.pop() - 1

print(answer)

3-3. C#

static void Main(string[] args)
{
    long answer = 0;
    int N = int.Parse(Console.ReadLine());

    int[] buildings = new int[N];
    Stack<int> stk = new Stack<int>();
    
    for (int i = 0; i < N; i++)
        buildings[i] = int.Parse(Console.ReadLine());

    for (int i = 0; i < N; i++)
    {
        while (stk.Count > 0 && buildings[stk.Peek()] <= buildings[i])
        {
            answer += i - stk.Pop() - 1;
        }
        stk.Push(i);
    }

    while (stk.Count > 0)
    {
        answer += N - stk.Pop() - 1;
    }

    Console.WriteLine(answer);
}