[백준알고리즘] 자료구조 - 1725번 히스토그램 문제(재도전할 문제)

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

1725번: 히스토그램

알고리즘 스터디원분께서 선정해주신 문제중 하나이다.

신나게 잘못 풀다 정신을 차려보니 생각보다도 더 어려운 문제였구나 느꼈다..

혼자서 처음부터 풀려다가는 시간이 끝도 없이 흐를 것 같아 다른 분들의 블로그들을 참고해가며 

풀이법을 최대한 이해하고 정리부터 하고 시작하기로 한다.

크게 분할정복 방식/스택 풀이방식 둘로 나뉘는 것 같은데 지금 스택을 복습중인 만큼 스택 풀이법을 참고했다.

나중에 스터디때 분할정복 방식을 공부하는 시점에서 분할정복식으로 다시 풀어보도록 해야겠다.

 

<최대한 이해해보고 적어보는 풀이 포인트>

 

n개의 막대들을 모두 이용하여 만들 수 있는 넓이는 그중 가장 높이가 낮은 막대이다.

아무리 다른 막대들이 더 높아봐야 결국 그중 가장 낮은 높이의 막대가 사각형의 높이가 될 수 있다.

 

스택의 top(top 체인이 스택에서 가장 높은 높이를 갖게된다)보다 더 높은 막대가 스택에 들어오게 되면 push

-> 이 경우 이전의 체인을 pop하여 없애지 않는다. 아직까진 필요한 정보이기 때문

 

그러나 top과 높이가 같거나 작은 i번째 막대가 들어오게 되면, 이 i번째 막대와 높이가 같거나 큰 스택의 체인들을 pop하는데

(새로 들어온 이 막대를 이용한 넓이를 구하려면 어차피 이 막대의 높이만큼의 사각형만을 만들 수 있을테니

이보다 크거나 같은 막대들의 높이는 필요없는 정보가 되기 때문)

이때!이 pop해버리는 스택의 원소들, 즉 각 체인의 넓이를 이 타이밍에 계산하게 된다.

i-1 인덱스에서 해당 체인 이전에 있는 체인의 인덱스를 빼면 pop하려는 체인의 width가 된다.

(이때 스택에 남아있는 이전 체인이 없다면 width는 처음부터 해당 막대의 인덱스, 즉 이 인덱스가 곧 width가 된다)

(앞에서부터 i-1까지가 width가 되어야 해당 체인으로 구성 가능한 사각형의 최대 가로길이가 됨)

이 과정에서 최대 넓이가 갱신된다.

i번째 막대보다 높이가 같거나 낮은 이전 체인들은 pop되어버리고,

새로 들어온 I번째 막대가 스택에 Push되어 새로운 체인이 구성되는것이다.

 

블로그 코드를 보니 좀더 생각정리가 되는 듯 하다.

이번에는 설명과 코드를 보며 이해하는 정도로 그쳤지만, 다음에는 꼭 직접 처음부터 끝까지 코드구현을 해보자. 재도전!!

 

https://st-lab.tistory.com/255

[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - JAVA [자바]

참고한 블로그!