[백준] 6198 파이썬(python) : 옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

 

 

이중 for문으로 풀었더니 시간초과가 나왔다. 그도 그럴게 이중for문으로 해결할 수 있는 간단한 문제가 골드 난이도를 가지고 있을것 같지 않았다.

 

이중for문으로 시간초과 나온 코드)

import sys
n = int(sys.stdin.readline())
building = [ int(sys.stdin.readline()) for _ in range(n) ]
answer, cnt = 0, 0
stack = []
for i in range(n-1):
    view = building[i]
    cnt = 0
    for j in range(i+1, n):
        if building[j] >= view:
            break
        elif building[j] < view:
            cnt += 1
    answer += cnt
print(answer)

 

monotone stack사용한 정답 코드)

import sys
n = int(sys.stdin.readline())
building = [ int(sys.stdin.readline()) for _ in range(n) ] #1
stack, res = [], 0 #2
for i in range(len(building)):
    while stack and building[stack[-1]] <= building[i]: #3
        stack.pop()
    stack.append(i) #4
    res += len(stack)-1 #5
print(res)

 

#1 : 빌딩의 높이 입력

#2 : 빈 스택과 결과값 출력할 변수 선언

#3, 4 : stack[-1]을 인덱스로 가지는 building의 값이 새로 들어올 값보다 작으면 stack을 계속 빼주고 마지막에 새로 들어올 원소를 삽입

#5 : 자기자신은 제외하고 추가

 

#5 은 현재위치의 빌딩을 볼 수 있는 빌딩의 수를 의미한다.

 

10 3 7 4 12 2 에서

0+1+1+2+0+1 = 5 이렇게 정답이 나온다.

즉 높이 3을 가진 빌딩을 볼 수 있는 빌딩은 1개라는 뜻이다.

 

큰 높이의 빌딩이 작은 높이의 빌딩을 내려다 볼 수 있다고 했고, 각 빌딩 마다 내려다 볼 수 있는 빌딩의 수를 세라고 말했으므로 각 위치의 빌딩에서 내림차순을 유지해야 한다. 그러므로 monotone stack알고리즘을 사용할 수 있다.

 

 

---

 

2812번 : 크게 만들기

 

2493번 : 탑