https://www.acmicpc.net/problem/1725
시간 0.7초, 메모리 128MB

https://www.acmicpc.net/problem/6549
시간 1초, 메모리 256MB

https://www.acmicpc.net/problem/14727
시간 2초, 메모리 256MB

input :

• N (1 ≤ N ≤ 100,000)
• 각 칸의 높이가 입력 됨.

output :

• 첫째 줄에 가장 큰 직사각형의 넓이를 출력

조건 :

• 히스토그램은 아래와 같은 막대그래프

• 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리도록 하자.

• 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성

---

3개의 문제는 동일한 문제이다. 결국 입력에 대한 것 중 가장 큰 직사각형의 넓이를 출력하라는 것이다.

맨 처음엔 정렬하면 되나? 했지만 이 건물들은 이동을 할 수 없기 때문에 주어진 조건들 만으로 문제를 해결해야 한다.

가장 먼저 든 생각은 그리디였다.
현재의 높이를 저장하다가 자기 보다 작은 게 나오면 업데이트를 하는 방식으로 말이다.
그런데 이렇게 하려고 하니 자기 보다 높은 게 나와서 바꾸려 할 때의 조건이 애매 했다.

이렇게 막히고 나서 백준님의 풀이를 보고 있었는데. 스택을 사용해서 현재의 위치를 x라 할 때 x + 1에 위치하는 건물의 높이가 자기 보다 낮으면 거리를 구해서 넓이를 구하고.
이를 누적하면서 문제를 해결할 수 있다 하였다.

스택

이런 풀이를 할 때는 스택을 주로 사용한다.
어차피 현 위치에서 스택에 존재하는 것들 중 가장 뒤에 있는 것 부터 확인을 하기 때문이다.
스택에 있는 건물의 높이를 비교해서 자기보다 크다면 현 위치의 건물 높이가 아닌 저장되어 있던 건물의 높이를 사용해서 넓이를 구할 수 있다.

중요한 것은 길이를 어떻게 구하는가 이다.

위치 i

i를 이용해서 계산을 하는 방식을 사용했다. 어차피 인덱스가 0에서 시작하니까 빼주는 것으로 사이에 존재하는 건물의 개수를 찾을 수 있다고 보았다.

더 이상 작은게 없을 때

그러니까 포인터가 배열의 끝까지 이동을 하고 나면 그 때도 넓이를 구해 줘야 한다.

이 때 사용한 방식은 그저 스택을 앞에서 부터 돌면서 저장되어 있는 위치를 배열의 길이에서 빼는 것으로 사이에 존재하는 건물의 개수를 세아렸다.

이 떄 저장되어 있는 위치에는 변화가 우선적으로 있어야 하는데
스택에 저장되는 건물을 생각해보면 자기 보다 이전에 존재하던 건물들은 자기 보다 크다는 것을 알 수 있다.
고로 while문을 통해 각 건물들을 꺼낼 때 이 인덱스들을 기억하고 있다가 그 값을 마지막에 저장을 하는 방식을 사용했다.

자연스럽게 업데이트를 하였다.

추가

다른 방식으로 i - 1 - height[-1][1]을 사용하는 방식이 있다.
이렇게 하게 된다면 배열의 가장 마지막에 0을 두어 언제나 계산을 하는 방식인데 아직 저 수식이 왜 사이 건물의 개수를 나타내는지는 모르겠다.

저거 말고 그냥 i를 쓰는 이유는 저장되어 있는 건물이 없으려면 이 건물은 0번째에 존재하거나 가장 마지막에 남아있는 건물이기 때문이다.

위의 업데이트 하는 방식을 쓰다가 i - 1 - height[-1]을 사용하려고 해서 그런것일 수도 있는데 나는 height에 존재하는 위치 값을 업데이트 하는 방식을 썼었기 때문에 동일하게 적용을 못하는 것일 수 도 있다.

다시 생각해보니까 결국 현재 pop()한 건물보다 작은 건물이 height[-1]에 저장될 것이다. 그런데 그냥 i - height[-1]을 해버리면 의도치 않게 height[-1]에 존재하는 건물도 계산에 포함되기 때문에 -1을 해준다.

import sys

n = int(sys.stdin.readline())
data = [int(sys.stdin.readline()) for _ in range(n)]

ans, height = -float('inf'), []
for i in range(len(data)):

    start_idx = -1
    while height and height[-1][0] > data[i]:
        value, start_idx = height.pop()
        ans = max(value * (i - start_idx), ans)

    if start_idx != -1:
        height.append([data[i], start_idx])
        continue

    height.append([data[i], i])

left = len(height)
for i in range(len(height)):
    ans = max(height[i][0] * (n - height[i][1]), ans)

print(ans)

히스토그램에서 가장 큰 직사각형을 찾는 것은 while문을 써줘야 하는 것과 입력이
한 줄에 들어오는 것이 다르다. 그 외의 것은 동일한 알고리즘을 통해 넓이를 구한다.

import sys

while True:
    temp = list(map(int, sys.stdin.readline().split()))
    if temp[0] == 0:
        break

    data = temp[1:]
    ans, height = -float('inf'), []
    for i in range(len(data)):

        start_idx = -1
        while height and height[-1][0] > data[i]:
            value, start_idx = height.pop()
            ans = max(value * (i - start_idx), ans)

        if start_idx != -1:
            height.append([data[i], start_idx])
            continue

        height.append([data[i], i])

    for i in range(len(height)):
        ans = max(height[i][0] * (temp[0] - height[i][1]), ans)

    print(ans)