백준 6549 자바 - 히스토그램에서 가장 큰 직사각형 (BOJ 6549 JAVA)

 

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

 

  코드가 긴 문제는 아니었지만, 공책에 그려보며 생각한걸 구현하기가 좀 어려웠다. 많이틀렸다 ㅋㅋ (맞았습니다가 여러개인 이유는 시간을 좀 더 줄여보려 했으나 유의미하게 시간차이를 못냈다.)

 

  풀고보니 사람들이 참 다양한 방법으로 푼 문제인것같다. 스택, 분할정복, 세그먼트 트리, 분리집합+우선순위 큐 크게는 이렇게 4가지 방식으로 푼 듯 하다. 저의 경우엔 스택으로 풀었다.

 

  높이(h)가 너비(n)에 비해 수치가 많이 크다. 처음 들었던 생각은 어차피 높이가 많다해도, n이 최대 10만이므로 h의 종류는 아무리 많아봐야 10만 가지이다. 따라서 좌표압축처럼 높이를 1~10만까지로 압축할 수 있다. (예를들어 높이가 3,5,2 처럼 들어왔다면 압축해서 2,3,1로 바꾸고 해당 수치를 인덱스로 쳐서 실제 높이를 저장해두면 구하는대는 문제가 없다.) 그럼 n에 대해 dp를 진행하며 각 높이별로 가능한 최대 연속된 n개를 구해볼 생각이었다.

하지만 일단 압축에는 정렬이 필요하고, 그럼 기본적으로 O(NlogN)이 필요한데 TC도 몇갠지 안주어진 마당에 빠듯하게 돌리긴 좀 무리가 있다고 생각했다. TC 갯수가 영향을 안끼칠정도면 n개에 대해 O(N) 수준의 알고리즘이 필요할꺼라 예상됬다. 그래서 dp 종류인가 생각도 해보고 여러가지로 생각해봤지만 일단 단순화 시켜서 생각해보기 위해 좌측부터 우측으로 점차 증가하는 형태와 점차 감소하는 형태를 나눠서 생각해봤다.

 

- 우선 높이(h)가 같거나 증가하는 경우이다.

이전과 비교해서 값이 같거나 증가하고 있다면, 아직까지는 넓이를 계산하는 것이 의미가 없다. n개를 모두 입력받았거나, 이후 감소하는 구간을 만나기 전까지는 넓이를 계산하지 않고 있다가 맨 마지막 지점에서만 계산해주면 된다. 직관적으로 맨 마지막 지점을 포함한 상태에서 다음과 같이 이전 높이들을 확인하면 될 것임을 예상할 수 있다.

 

 

즉, 높이가 동일하거나 증가하는 경우 맨 마지막 지점에서 이전 지점 모두 중 의미가 있는 넓이는 모두 계산할 수 있다.

 

 

- 다음은 높이(h)가 감소하는 경우이다.

이번엔 좌측에서 우측으로 진행할 때, 언제 넓이를 확인해야 할까? 증가하는 경우와는 반대로 매번 확인해야 한다. n을 맨 마지막 지점을 포함한 채로는 그 이전의 넓이를 계산할 수 없다. 즉 n이 진행됨에 따라 다음과 같이 살펴봐야 한다.

 

 

 

- 자 그럼 둘을 통합해서 로직을 만들자.

  로직을 정리하면, [ 동일하거나 증가하는 동안은 넓이를 체크하지 않으며 이전 높이들만 기록해두고, 그 끝(감소하거나 히스토그램이 끝남)을 만날 때 마지막 지점에서 전부 계산한다! ]가 된다.

 

  이전 높이를 가져올 수 있도록 스택 자료구조를 사용한다. 그리고 각 n 지점을 순회하며 높이를 입력받고 (22line),

1. 스택이 비었거나 높이가 이전과 동일하거나 증가한다면 넓이를 계산하지 않고 스택에 넣는다. (32line)

 

2. 높이가 이전보다 낮아졌다면, 현재 스택의 상태는 '1'에서 넣었던 동일하거나 증가하는 상태일 것이다. 따라서 스택이 비거나, 현재 높이보다 큰 부분까지 빼면서 넓이를 계산한다. 즉, 위에서 그려뒀던 이미지 중 높이가 같거나 증가하는 동안에 해당하는 로직을 수행한다. (35line popStackUntilH 함수) 그 후에 현재 지점의 높이를 다시 스택에 넣는다. (36line)

 

* 주의 : 감소할 때 스택 전체를 빼지않고 현재 높이보다 큰 부분까지만 빼는 이유는 다음과 같은 경우를 처리하기 위해서이다. (이것때매 여러번 틀림..)

 

3. 히스토그램의 끝을 만났을 때에도 동일하게 수행한다. (38line) -> 다만 이 때는 남은건 전부 빼야 하므로 현재 높이가 0이라고 치면 모두 뺄 수 있다. (curIdx == n ? 0 : arr[curIdx]; 부분)

 

이걸 코드로 구현하면 다음과 같다.

 

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/06500/BOJ_6549.java