1725번: 히스토그램
첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은
www.acmicpc.net
## 접근
이 문제는 시간복잡도에 유의해서 풀어야 한다. 만약에, 각 시작점마다 최고 넓이를 구하게 된다면, 시간 복잡도는 N * N으로 시간 초과가 발생하게 된다.
이 문제를 스택을 이용하면 시간 복잡도 N만에 문제를 해결할 수 있다. 문제를 자세히 살펴보자.
어떤 특정 시작점에서 자신보다 낮은 높이의 직사각형을 만나게 되면, 히스토그램을 더 이상 그릴 수 없다.
어떤 특정 시작점에서 자신보다 높은 높이의 직사각형을 만나게 되면, 히스토그램을 그릴 수 있다.
따라서, 스택 자료구조에서 각 높이들을 보관해두어야 한다. 각 높이들은, 항상 오름차순으로 정렬되어 있을 것이다. 스택에서 Pop 연산이 이루어지려면, 현재 탐색하고 있는 히스토그램보다 스택의 아이템이 클 때 발생할 수 있다.
Pop 연산이 발생할 때마다, Pop된 높이에서 그릴 수 있는 최대의 넓이를 구해주면서 최댓값을 갱신하면 된다.
## 해설코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N;
static Stack<Item> stk = new Stack<>();
static long answer = 0;
static long num;
static class Item{
long idx, h;
Item(long idx, long h){
this.idx = idx;
this.h = h;
}
}
public static void main (String[] args) throws java.lang.Exception
{
N = Integer.valueOf(br.readLine());
for(int i = 0; i < N; i++){
num = Long.valueOf(br.readLine());
while(!stk.isEmpty() && stk.peek().h > num) {
long getH = stk.pop().h;
long width = i;
if(!stk.isEmpty())
width -= stk.peek().idx + 1;
answer = Math.max(answer, getH * width);
}
stk.push(new Item(i, num));
}
while(!stk.isEmpty()) {
long getH = stk.pop().h;
long width = N;
if(!stk.isEmpty())
width -= stk.peek().idx + 1;
answer = Math.max(answer, getH * width);
}
System.out.println(answer);
}
}
|