알고리즘 & BOJ 1725 히스토그램(C++)

BOJ 링크 

1214 : 히스토그램

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 760 회    시도횟수: 3602 회   

히스토그램이란 보통 분포의 정도를 알기 위해 사각형의 서열을 기준선에 맞춰 늘어놓은 다각형을 말한다. 만약 임의의 수열이 2, 1, 4, 5, 1, 3, 3일 경우 사각형의 너비를 1로 맞추어 히스토그램으로 만들면 다음과 같다.

 

  

우리가 하고자 하는 것은 임의의 히스토그램이 주어졌을 때 히스토그램 내에서 사각형으로 이루어진 가장 큰 면적의 크기를 알고자 한다. 왼쪽 의 히스토그램에서 가장 큰 사각형의 영역은 오른쪽에 밑줄이 쳐진 영역과 같다

 

입력 첫 번째는 히스토그램을 이루는 사각형의 개수 n(n≤100,000)이 입력되고 그 뒤로 히스토그램을 이루는 사각형의 높이가 순서대로 n개 입력이 된다. 사각형의 높이 k는 0 ≤ k ≤ 1,000,000,000 이다. 사각형의 너비는 모두 1이다.

입력된 히스토그램으로 만들 수 있는 사각형의 최대 면적을 출력하라.

[Copy] 7 2 1 4 5 1 3 3

[Copy] 8

출처 : Ulm local 2003

?

/************************************************************** Problem: 1214 User: a132034 Language: C++ Result: Success Time:1 ms Memory:4564 kb ****************************************************************/ #include <stdio.h> #include <vector> #pragma warning (disable:4996) struct hist { long long int h; long long int r; long long int l; }; static hist H[111111]; std::pair<int, int> S[111111]; //<히스토그램 높이, 히스토그램 인덱스> int main() { int N; scanf("%d", &N); int top = 0; for (int i = 1; i <= N; ++i) { int tmp; scanf("%d", &tmp); H[i].h = tmp; H[i].r = i; H[i].l = i; } for (int i = 1; i <= N; ++i) { if (S[top].first <= H[i].h)//이전 들어있는 값 보다 큰 경우 혹은같은 경우 { S[++top].first = H[i].h; S[top].second = i; //해당 인덱스 저장 } else { while (S[top].first > H[i].h) //스택에 히스토그램이 있고 그 높이가 입력받은 높이보다 큰 경우 H[S[top--].second].r = i - 1; S[++top].first = H[i].h; S[top].second = i; } } while (top > 0) H[S[top--].second].r = N; top = 0; for (int i = N; i >= 1; --i) { if (S[top].first <= H[i].h) { S[++top].first = H[i].h; S[top].second = i; } else { while (S[top].first > H[i].h && top > 0) H[S[top--].second].l = i + 1; S[++top].first = H[i].h; S[top].second = i; } } while (top > 0) H[S[top--].second].l = 1; long long max = 0; for (int i = 1; i <= N; ++i) { if (H[i].h * (H[i].r - H[i].l + 1) > max) max = H[i].h * (H[i].r - H[i].l + 1); } printf("%llu", max); return 0; }

두 곳의 문제가 동일하나 범위가 약간 다른데 Jungol에서 더 넓은 범위를 사용한다. 

문제 푸는 방법은 일단.. 

생각해 볼 수 있는 가장 기본적인 방법은 각 히스토그램의 위치별로 가장 큰 직사각형의 넓이를 구하고 그 중 가장 큰 것을 찾는 방법이다. 

그렇게 한다면 아래와 같은 방법을 사용할 수 있다. 

히스토그램 H가 있을 때 H[i]를 i번째 높이에서 가능한 히스토그램의 최대 넓이라고 정의한다면 

좌 우로 i번째 히스토그램보다 작은 히스토그램이 나오기 전 까지 모든 히스토그램을 찾은 후에 i번쨰 히스토그램의 높이를 곱해주면 된다. 

예를들어 

2 1 4 5 1 3 3 (샘플 입력)높이의 히스토그램이 있을 경우 

     ^ <- 높이가 4인 히스토그램에 대해 최대 넓이를 구하려면 좌측으로 4보다 작은수가 나오기 전 까지, 우측으로 4보다 작은수가 나오기 전 까지 가능하므로 좌측으로는 5, 우측으로는 자기자신인 4 까지 가능하다. 넓이는 2 * 4(높이)

모든 입력값 n개에 대해서 최악의 경우 n개 모두 n개를 전부 봐야 하므로 (전체가 1인 경우 양옆이 1보다 작기 전 까지 계속 보게 될 것이므로...) 

O(n^2)가 될 것이다. 

n은최대  10^5 이므로 n^2 이면 10^10의 연산을 해야 한다. 

대략 초당 연산을 1억번정도 할 수 있을때, 100초정도의 시간이 걸린다고 할 수 있다. 

(물론 요즘 cpu는 더 빠르겠지만... 대략적으로 계산할 때 이렇게 계산하면 편하다.)

시간을 줄이기 위해서 스택을 사용하였다. 

스택에 값을 차례대로 넣어주며 자신보다 낮은 높이의 값이 들어올 때 스택에서 들어오는 값 보다 높은 값은 전부 제거해주며 제거하면서 right값을 지정해준다. 

반대로 하면서 left값을 지정해 준다. 

r-l+1을 하면 각각의 히스토그램 위치에서 최대 넓이를 구할 수 있다. 

이렇게 하면 n + n의 연산으로 구할 수 있으므로 O(n)이 된다. 

2 1 4 5 1 3 3을 기준으로 예를 들자면. 

1. 스택에 2가 들어온다. 비었으므로 들어온다. 

STACK : 2

2. 스택에 1이 들어오려고 했더니 2가 들어올 1보다 크므로 2의 right는 1(자기자신위치)이 된다. 2을 빼주며 2의 R=1으로 설정하고 1을 넣는다. 

STACK : 1

2. 스택에 4가 들어온다. 1보다 크므로 들어온다. 

STACK : 1 4

3. 스택에 5가 들어온다. 4보다 크므로 들어온다. 

STACK : 1 4 5

4. 스택에 1이 들어온다. 5는 1보다 크므로 빼준다. 4도 빼준다. 4,5의 R=4(5의 위치가 4이므로)가 된다. 1을 스택에 넣는다.

STACK : 1 1

5. 스택에 3이 들어온다. 1보다 크므로 들어온다. 

STACK : 1 1 3

6. 스택에 3이 들어온다. 3과 동일하므로 들어온다(크거나 같으면 가능) 

STACK : 1 1 3 3

7. 모든 루프가 끝났다. 남은 수는 모두 R이 7(최대길이)이 된다. 

반대로도 한번 해준다. 3 3 1 5 4 1 2 순서로 해준다면 L을 구할 수 있을 것이다. 

최대값은 4를 기준으로 R은 5의 위치인 2, L은 자기자신인 4 이므로 R-L+1 = 2 

2 * 4(높이) = 8이 된다. (모든 값을 한번식 보며 (R-L+1)*H(높이) 를 하면서 비교하면 된다.)