[백준/자료구조] 6198: 옥상 정원 꾸미기 - 파이썬

문제

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

6198번: 옥상 정원 꾸미기

 

오답 풀이 (시간초과)

아래 풀이는 시간초과가 발생한 풀이이다.

 

단순하게 i 번째 원소가 i+1 번째부터 전체 원소까지 탐색할 때 큰 원소를 만나면 인덱스 사이의 거리를 구해

결과에 추가하는 방법으로 코드를 작성하였는데 이렇게 하면 너무 많이 for문을 돌아서 시간초과가 발생한다.

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
apart = deque(0 for _ in range(n))
view = deque(0 for _ in range(n))
for i in range(n):
    apart[i] = (int(input()))

def sol(i):
    j = i+1

    while j != len(apart):

        if apart[i] < apart[j]:
            view[i] = (j-i-1)
            return
        j += 1
    view[i] = (j-i-1)

for a in range(len(apart)-1):
    sol(a)

print(sum(view))

 

풀이

이 풀이는 스택 자료구조를 이용하여 스택의 길이를 통해 빌딩의 수를 구하였다.

n = int(input())
arr = [int(input()) for i in range(n)]
stk = []
result = 0

for i in range(n):
    print(stk)
    while stk and stk[-1] <= arr[i]:
        stk.pop()
    stk.append(arr[i])
    result += len(stk) - 1

print(result)

 

어떻게 돌아가는지 각 과정을 출력해 보았다.

[]
[10]
result 0

[10]
[10, 3]
result 1

[10, 3]
[10, 7]
result 2

[10, 7]
[10, 7, 4]
result 4

[10, 7, 4]
[12]
result 4

[12]
[12, 2]
result 5

 

    while stk and stk[-1] <= arr[i]:
        stk.pop()

이 코드를 잘 살펴봐야 하는데,

stack이 빌 때까지 또는 stack의 맨 오른쪽 원소가 탐색중인 해당 빌딩의 원소보다 작을때까지 연산을 수행한다. 

맨 오른쪽 원소가 빌딩을 탐색중인 해당 원소보다 작다면 맨 오른쪽 원소를 pop연산을 통해 stack에서 제거한다

[10, 3]
[10, 7]

stack의 맨 오른쪽 원소가 3이였는데 탐색중인 7을 만나 3이 pop되고 7이 stack에 입력되었다.

 

[10, 7, 4]
[12]
result 4

여기서도 stack의 맨 오른쪽 원소가 탐색중인 빌딩의 원소보다 작아서 10, 7, 4 가 전부 pop되고 12가 stack에 들어가 있다.

 

여기서 빌딩을 탐색하면서 스택의 길이는 해당 위치의 빌딩을 몇 개의 빌딩이 바라볼 수 있는지 나타낸 것이다.

인덱스를 돌면서 스택의 길이들을 전부 합하면 각 빌딩이 오른쪽으로 볼 수 있는 빌딩의 수를 나타낼 수 있다.