👀 문제
https://www.acmicpc.net/problem/6549
👊 도전
1. 설계
- 스택을 이용한다.
- height[top]>height[i]이면 top과 i를 포함하여 넓이를 만들 수 있으므로 pop하여 넓이를 계산한다.
- 나보다 작은 높이 top이 나올 때까지 계속 계산한다.
- 계산이 끝나면 i 뒤에서 나중에 i를 체크해볼 수 있도록 push
- n까지 체크가 끝나면 스택에 남은 값들도 계산해준다.
2. 구현 (성공 코드)
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
import java.util.*;
import java.io.*;
/**
* @author HEESOO
*
*/
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while(true) {
st=new StringTokenizer(br.readLine());
int n=Integer.parseInt(st.nextToken());
if(n==0) break;
int[] height=new int[n];
Stack<Integer> stack=new Stack<>();
long max=0;
for(int i=0;i<n;i++) { // 높이 저장
height[i]=Integer.parseInt(st.nextToken());
}
for(int i=0;i<n;i++) { // i 포함 왼쪽으로 만들수 있는 넓이 체크함
// 왼쪽에 나보다 큰 높이 발견->걔 포함해서 넓이 만들 수 있음
while(!stack.isEmpty() && height[stack.peek()]>height[i]) {
int idx=stack.pop();
// 맨 왼쪽에서 i까지이면 width=i, 부분 구간이면 ~.
int width= stack.isEmpty()? i: i-stack.peek()-1;
max=Math.max(max, (long)width*height[idx]);
}
stack.push(i);
}
// 남은 값들도 계산
while(!stack.isEmpty()) {
int idx=stack.pop();
int width= stack.isEmpty()? n: n-stack.peek()-1;
max=Math.max(max, (long)width*height[idx]);
}
System.out.println(max);
}
}
}
3. 결과
🤟 성공 🤟
이 문제 리트코드에서도 보고 꽤 많이 봤는데 아직도 잘 못 풀겠다.
넓이 계산하면서 int형을 벗어날 수 있다는 것을 몰라 실패했다.
4. 설명
- 스택을 이용한다
- 세그먼트 트리로도 해결할 수 있다. 근데 스택이 더 익숙해서 스택 코드를 이해하려고 노력했다.
- i로 0~n까지 순회하며 넓이를 체크한다. i 기준 왼쪽으로 만들 수 있는 넓이를 계산한다.
- 일단 넓이 계산이 끝나면, 다음 사용을 위해 i를 push해야 한다.
- 넓이 계산은 스택의 top을 비교하면서 진행한다.
- h[top]>h[i]여야 top을 포함하여 넓이를 계산할 수 있다.
- 0~i까지 넓이를 구하는 것이라면 width=i, 그게 아니라면 i-st.top-1(이해 안됨).
- 높이는 i가 기준이므로 width*height[i]이 넓이가 된다.
- 최대 넓이를 구해야하므로 Math.max()를 이용하여 max에 최댓값을 넣는다.
- n까지 순회가 끝난 후, 스택을 확인하여 아직 값이 남아있다면 스택 top~n(마지막)까지의 넓이를 계산해준다.
5. 성능
- 시간 복잡도: O(N)
for문 탐색 N, 안에 while문은 N 이하의 시간, for 밖의 while도 N 이하의 시간 - 공간 복잡도: O(N)
height 배열 사이즈 N, 스택 사이즈 최대 N
👏 해결 완료!
참고
- 백준 6549 히스토그램에서 가장 큰 직사각형 Java https://dundung.tistory.com/96
- [BOJ 백준] 히스토그램에서 가장 큰 직사각형(6549) Java https://subbak2.tistory.com/25