백준 - 옥상 정원 꾸미기 (feat.Python)

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

• 풀이 1

import sys
input = lambda : sys.stdin.readline().rstrip()
write = lambda x : sys.stdout.write(str(x)+"\n")
# (1 ≤ N ≤ 80,000) -> O(n^2) 미만의 알고리즘 사용해야 함
n = int(input())
stack = []
counts = [0]* n
for i in range(n):
    h = int(input())
    if stack:
        while(stack[-1][1] <= h):
            p_idx, p_h = stack.pop()
            if stack:
                counts[stack[-1][0]] += counts[p_idx]
            else: break
    if stack and stack[-1][1] > h:
        counts[stack[-1][0]] += 1

    stack.append((i, h))

# 스택에 남은 빌딩이 있을 수도 있으니까
if stack:
    while(1):
        p_idx, p_h = stack.pop()
        if stack:
            counts[stack[-1][0]] += counts[p_idx]
        else: break

write(sum(counts))

• 풀이 2 : MJ Studio님의 풀이
  마지막에 더미 데이터를 추가하는 방법은 생각치도 못했다..
  제 풀이가 좀 부끄럽네요..

  명주피셜 : 문제를 풀 때 코드를 일관성있게 작성하기 위해 더미 데이터를 맨 앞, 맨 뒤 혹은 어디든 추가해서 데이터를 전처리하고 시작하기도 합니다.

n = int(input())
h = [int(input()) for _ in range(n)]

h.append(int(1e9+1)) # 더미 데이터 추가
n += 1

answer = 0
stack = []

for i in range(n):
    while len(stack) and stack[-1][0] <= h[i]:
        answer += i - stack[-1][1] - 1 # 현재 idx - 스택의 마지막 요소의 idx + 1
        stack.pop()
    stack.append([h[i], i])

print(answer)

이 문제를 풀었으면 히스토그램에서 가장 큰 직사각형이 문제를 풀어보시는 걸 추천합니다 :D
이 문제는 관리인이 왼쪽, 오른쪽 모두 볼 수 있는 문제입니다.