[AC] 6549 히스토그램에서 가장 큰 직사각형

출처 : https://www.acmicpc.net/problem/6549

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/6549.cpp

이 문제는 상당히 애를 먹었고 시간을 엄청 쏟아부었다. 

정말 쉽지 않은 문제였다. 처음에는 세그먼트트리로 접근을 하였으나 도무지 답에 근접할수가없었고, 시간상 무조건 TL이 나오는 설계만 나왔다. 시간을 더줄이기위한 풀이법을 생각하다가 이렇게도 저렇게도 안되어 고민하고있던차에 문제분류를 보니 스택도 가능하다고 하여 스택을 생각해봤다.

만약 이 문제를 스택으로 푼다면..스택에는 어떤데이터가 들어가야할까? 

높이 혹은 해당인덱스가 들어가야할것 같았다. 그리고 생각한게 어떤 규칙을 사용하여 스택에 넣을것인가?

점점 줄어들게 넣을것인가? 점점 증가되게 넣을것인가? 여기서 계속 생각하다가 점점 줄어들게 스택을 구성하면 예제도 풀기 어려워 반대로 생각하였다. 

점점 증가하도록 구성하고 만약 인풋이 작다면 새로 넣어주기 전에 넓이를 계산하게 하였다. 여기서 다시 엄청난 시간을 소모하였다. 어떻게 넓이를 구할것인가? 예제는 구했으나 수차례 오답을 맞았고 특이 케이스를 찾아냈다. 

만약 인풋이

7 101 321 128 50 68 99 100

라면 정답은 50을 기준으로 전부 계산한 350이 나와야 한다. 그러나 내가만든 풀이는 좀처럼 이 케이스를 계산하지 못하였다.

그리고 구한 풀이는 다음과 같다.

1. 스택이 비어있거나 스택의 탑보다 현재 인풋이 크다면 그냥 스택에 푸시한다.

2. 1번에서 그렇지 않다면 스택을 비우면서 계산을 한다. 계산은 다음과 같이 진행한다.

1) 먼저 스택의 탑보다 현재 입력이 커지면 스택을 그만 비우고 종료를 한다.

2) 그 경우가 아니라면 top을 현재의 스택탑으로 만들고 하나를 제거한다.

3) 다시 새로운 찹을 left에 담아둔다. 즉 현재최고막대기에서 그 바로다음막대기에 해당한다. 

4) 하지만 스택이 비어있다면 left를 -1로 값을 만든다.

5) 넓이를 구하는데 넓이는 현재 최고 막대기길이*(현재 인덱스 - left -1)을 해준다. 왜 이렇게 구성이되냐면 만약 예제처럼 4 5 1이 들어왔을때 일단 4 5 가 스택에 있을텐데 현재인덱스(4)-left(4가 위치한 인덱스인 2)-1 or (left+1) 을 하면 현재 5가 가진 최고 넓이가 나오고 다시 이제 왼쪽으로가면 현재인덱스 4에서 1이 위치한 1번으로오고 다시 그 직전까지의 넓이를 계산하여 최대값을 갱신하는 방식이다. 

3. 위 과정으로 스택을 점점 증가하도록 구성하는데 입력이 종료되면 이제 스택을 끝까지 비우면서 위과정을 실행한다. 그런데 여기서 만약 스택이 완전히 비어진다면 즉, 완전히 비어지기전 녀석은 현재 인풋중 가장 작은녀석을 의미하는데 이녀석은 전체 길이만큼 곱해주면 되는 특별한 경우가 된다. 

여기서 나는 만약 내가 만든 인풋에서 68이 51이면 값이 변할수있지 않을까 생각했는데 그렇다면 결국 50이라는 값을 버리게 되므로 값이 작아지고 68이라고해도 전수가 만약 1인 경우도 생각해봤는데 이때는 앞에서 계산한 맥스값은 321이 되고 현재 스택에는 1 68 99 100 이 있는데 68일때는 1때문에 완전 분할되버리기때문에 불가하다. 

암튼 문제를 이해하면서 자가당착에 빠져 조금 혼란스러웠지만 결국 풀어내긴하였다. 상당히 애먹은 문제이다.