[백준(BOJ)] #1725- 히스토그램 (파이썬, PyPy3)

문제

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

1725번: 히스토그램

 

---

문제 풀이

스택 자료구조 사용, 백준 블로그 참고

2022.06.29 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue)

[파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue)

https://www.acmicpc.net/blog/view/12

히스토그램에서 가장 큰 직사각형

 

위와 같은 히스토그램이 주어졌을 때 스택 자료구조를 사용하여 어떻게 가장 큰 직사각형을 찾는지 알아보겠습니다.

 

1) 1행의 인덱스와 높이의 쌍을 스택에 저장합니다. 

 

2) 스택 제일 위에 2행의 높이보다 높이가 더 큰 행의 정보가 있는지 확인합니다. 스택 제일 위에 저장되어 있는 1행의 높이는 2행의 높이보다 큽니다. 

 

3) 스택에서 pop을 하여 너비를 구해줍니다. 높이는 2이고, 2행의 인덱스 1에서 1행의 인덱스 0을 빼므로 너비는 2 * (1-0) = 2가 됩니다. 현재 최대 너비는 2입니다. * 이 과정을 스택 제일 위에 있는 행의 높이가 현재 행의 높이보다 크면 계속해주고, 이때 행의 인덱스를 따로 저장합니다. 이 과정을 마치고 나면 따로 저장한 행의 인덱스는 0이고, 현재 행의 높이 1과 쌍으로 스택에 저장합니다. 

 

 

* 모든 막대 x에 대해서 x를 높이로 하면서 만들 수 있는 가장 큰 직사각형을 찾아야하고, 현재 행의 높이보다 크지 않은 높이를 가진 행의 인덱스를 저장하기 때문에 현재 행의 높이를 높이로 하면서 만들 수 있는 가장 큰 직사각형을 찾을 수 있음 

4) 3행의 인덱스와 높이의 쌍을 스택에 저장합니다.

 

5) 4행의 인덱스와 높이의 쌍을 스택에 저장합니다.

 

6) 5행의 높이 1은 스택 제일 위에 저장되어 있는 4행의 높이 5보다 작습니다. 4행의 데이터를 pop 하여 행의 차와 높이를 이용하여 너비를 구합니다. 행의 인덱스 차는 1(4-3)이고, 높이는 5이므로 너비는 5가 됩니다. 앞에서 구했던 너비 2보다 크므로 최대 너비는 5가 됩니다. 

 

7) 5행의 높이 1은 스택 제일 위에 저장되어 있는 3행의 높이 4보다 작습니다. 3행의 데이터를 pop하여 행의 차와 높이를 이용하여 너비를 구합니다. 행의 인덱스 차는 2(4-2)이고, 높이는 4이므로 너비는 8이 됩니다. 앞에서 구했던 너비 5보다 크므로 최대 너비는 8이 됩니다. 

 

8) 스택에 5행의 높이보다 높이가 큰 행의 정보가 없으므로 현재 행의 높이 1과 3행의 인덱스 2를 스택에 저장합니다. 

 

9) 6행의 인덱스와 높이의 쌍을 스택에 저장합니다.

 

10) 7행의 인덱스와 높이의 쌍을 스택에 저장합니다.

 

11) 마지막으로 높이가 0인 8행이 있다고 가정하고 비교합니다. 스택에 저장되어 있는 7행에 대해 너비를 구해줍니다. 행의 인덱스 차는 1(7-6)이고, 높이는 3이므로 너비는 3이 됩니다. 앞에서 구했던 최대 너비 8보다 작으므로 갱신하지 않습니다.

 

12) 스택에 저장되어 있는 6행에 대해 너비를 구해줍니다. 행의 인덱스 차는 2(7-5)이고, 높이는 3이므로 너비는 6이 됩니다. 앞에서 구했던 최대 너비 8보다 작으므로 갱신하지 않습니다.

 

13) 스택에 저장되어 있는 3행에 대해 너비를 구해줍니다. 행의 인덱스 차는 5(7-2)이고, 높이는 1이므로 너비는 5가 됩니다. 앞에서 구했던 최대 너비 8보다 작으므로 갱신하지 않습니다.

 

14) 스택에 저장되어 있는 1행에 대해 너비를 구해줍니다. 행의 인덱스 차는 7(7-0)이고, 높이는 1이므로 너비는 7가 됩니다. 앞에서 구했던 최대 너비 8보다 작으므로 갱신하지 않습니다.

 

따라서 최대 너비는 8입니다.

 

---

구현

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    res = 0
    graph = list()
    for _ in range(n):
        graph.append(int(input()))
    graph.append(0)

    stack = list()
    stack.append((0, graph[0]))
    left = 0

    for i in range(1, n+1):
        left = i
        while stack and stack[-1][1] > graph[i]:
            left, h = stack.pop()
            res = max(res, (i-left) * h)
        stack.append((left, graph[i]))

    print(res)

결과