[세그먼트 트리, 분할정복] 백준 6549번 히스토그램에서 가장 큰 직사각형 자바(java) 풀이

BOJ 6549번 히스토그램에서 가장 큰 직사각형 문제 자바(java) 풀이

• 랭크 : 골드1
• 백준 6549번 히스토그램에서 가장 큰 직사각형
  
  
  

문제 정리

1. 히스토그램: 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형
2. 각 직사각형을 같은 너비를 가지지만 높이가 다를 수 있다.
3. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.
   
   
   

문제 풀이

우선 넓이를 어떻게 구해야 하는지 파악해야 합니다.
넓이는 구간에서 높이가 작은 직사각형에 depend 됩니다.
만약 1-3구간에서의 높이가 [3,1,2]라면 높이 1이 가장 작기 때문에 이 구간에서의 넓이는 1x3(구간의 길이)=3이 됩니다.
이 방식을 이용해서 1-1, 1-2, 1-3, ... 1-n
2-1, 2-2, 2-3, ... 2-n
... n-n 까지 이중 for문을 이용해서 O(n^2)에 구할 수 있습니다.


1. O(n^2)을 이용한 최대 넓이 구하기
하지만 이 방법은 n이 크기 때문에 시간초과가 발생 합니다.

    int maxSum = 0;
    for(int i=0; i<n; i++){
        int max = arr[i];
        int min = arr[i];
        for(int j=i+1; j<n; j++){
            int sum = 0;
            if(max < arr[j]){
                max = arr[j];
                sum = min*(j-i+1);
            }
            else if(max > arr[i]){
                min = min > arr[j] ? arr[j] : min;
                sum = min*(j-i+1);
                break;
            }
            else{
                min = min > arr[j] ? arr[j] : min;
                sum = min*(j-i+1);
            }
            maxSum = maxSum < sum ? sum : maxSum;
        }
    }
    System.out.println(maxSum);

2. Segment Tree를 이용하여 O(NlogN)에 구하기
segment tree를 응용하여 구간에서의 최대 넓이를 구할 수 있습니다.

1. 각 말단 노드는 인덱스를 갖습니다.
2. 그의 부모 노드들은 자식 중에 더 작은 높이를 갖는 인덱스를 갖습니다.
   예를 들어 0,1을 자식으로 갖는 부모는 1을 갖게 됩니다.
   왜냐하면 0번째 직사각형의 높이는 2, 1번째는 1로 더 작기 때문에 그 인덱스인 1을 갖습니다.
3. 위와 같은 방식으로 segment tree를 만듭니다.
4. 그리고 구간을 나눠가며 최대값을 갱신합니다.
   이때 중요한 것은 최소의 인덱스를 빼고 양쪽으로 나눠서 값을 구해나가면 됩니다.
   왜냐하면 구간에서 넓이는 최소 높이에 depend 되기 때문에 최소 높이를 갖는 index를 빼면 다른 구간에서 다른 최소 높이를 구해 나올 수 있는 가능한 넓이를 구할 수 있기 때문입니다.
5. 아래 그림과 같은 방식으로 구해가며 최대 넓이를 갱신합니다
   세그먼트 트리로 답을 구하는 과정을 도식화하면 아래 그림과 같습니다.

   

3. 분할정복 이용하여 O(NlogN)에 구하기
원래 구해야 하는 것은 [1,n]범위 중에서 직사각형의 최대 넓이를 구하는 것입니다.
이 것을 잘게 쪼갭니다. 범위를 나눠서 계산 하는 것을 분할 한다고 생각합니다.
n을 반으로 나누고 다시 n을 반으로 나누고 [1,1], [2,2] ... [n,n] 처럼 하나로 나눠질 때 까지 나누고 합칩니다.

1. 양쪽으로 나눠가며 양쪽에서 더 큰 넓이를 반환합니다.
2. 그리고 나눠진 구간에 걸치는 범위에 있는 직사각형의 넓이를 조사합니다.
   조사할때 직사각형의 높이가 큰 쪽으로만 확장해 나갑니다.
   왜냐하면 직사각형의 넓이는 최소 높이에 depend 되기 때문입니다.
   높이가 작은 곳으로 확장하게 되면 어차피 작아지게 되기 때문입니다.
3. 범위를 벗어나기 전까지 확장합니다.
   양쪽으로 모두 범위를 넘지 않은 경우,
   오른쪽 범위를 넘은 경우,
   왼쪽 범위를 넘은 경우 이렇게 3가지 경우로 나눠서 최소 높이를 찾아서 넓이를 계산해 더 크다면 갱신해줍니다.
   분할정복으로 답을 구하는 과정을 도식화하면 아래 그림과 같습니다.

• 파란색: 양쪽으로 나눠서 계산
• 초록색: 양쪽에 걸친 구간 계산
  

  

6549번 히스토그램에서 가장 큰 직사각형 자바(java) 코드(분할정복)

 

 

6549번 히스토그램에서 가장 큰 직사각형 자바(java) 코드(세그먼트 트리)