[백준] 6549 히스토그램에서 가장 큰 직사각형 - Java
https://13months.tistory.com/100
[백준] 1725 히스토그램 - Java
스택에 인덱스를 넣어주고 따로 배열을 설정해 배열에는 직사각형의 높이에 대한 정보를 넣었다. 넓이를 구하는 과정은 이전에 탐색한 직사각형의 높이가 현재 탐색하고 있는 직사각형의 높이
13months.tistory.com
위의 문제를 풀고 오니 이번 문제는 덤으로 같이 주는 느낌이였다.
입력 방법의 차이가 있을 뿐 풀이법은 같다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
while (true) { // while 루프의 시작
String[] temparr = sc.nextLine().split(" ");
int[] heightarr1 = new int[temparr.length];
for (int i = 0; i < heightarr1.length; i++) {
heightarr1[i] = Integer.parseInt(temparr[i]);
} // 높이 정보 입력. 배열에다가 입력해준다.
if (heightarr1[0] == 0 && heightarr1.length == 1) {
break;
} // 탈출구
int[] heightarr = new int[heightarr1.length-1];
for(int i=0; i<heightarr.length; i++) {
heightarr[i] = heightarr1[i+1];
}
// 여기까지는 입력부분
Stack<Integer> st = new Stack<>();
long maxvalue = 0;
for (int i = 0; i < heightarr.length; i++) {
// 스택에는 인덱스를 담고, heightarr에는 높이 정보를 담는다.
while (st.isEmpty() == false && heightarr[st.peek()] >= heightarr[i]) {
// 스택이 비어있지 않고 지금 탐색하는 막대의 높이가 바로 전에 탐색한 막대의 높이보다 작거나 같으면 (이전이 더 크면)
// 과거 막대들을 pop 하면서 넓이를 구한다.
//이때 pop 하는 막대들의 높이는 heightarr[i] 보다 작거나 같은걸로..
long height = heightarr[st.pop()];
// 높이를 바로 전에 탐색한 막대의 높이로 설정하고 pop 진행
long width = 0;
if (st.isEmpty()) {
// pop한 다음에 스택이 비어있으면, 즉 0~ i-1 가 폭이 된다.
width = i;
} else {
width = i - 1 - st.peek();
// pop한 다음 스택이 비어있지 않으면 최댓값을 계속 갱신시킨다.
// 체인의 폭은 i-1-가장최근인덱스
}
maxvalue = Math.max(maxvalue, width * height);
}
st.push(i);
// 스택이 비어있을때까지 수행하고 비어있으면 인덱스를 넣어준다.
}
while (st.isEmpty() == false) {
long height = heightarr[st.pop()];
long width = 0;
if (st.isEmpty()) {
width = heightarr.length;
} else {
width = heightarr.length - 1 - st.peek();
}
maxvalue = Math.max(maxvalue, width * height);
}
sb.append(maxvalue).append("\n");
} // while 루프의 끝
System.out.println(sb);
}
}
'Algorithm > Baekjoon' 카테고리의 다른 글
[백준] 1725 히스토그램 - Java (0) | 2021.11.17 |
---|---|
[백준] 1016 제곱ㄴㄴ수 - Java (0) | 2021.11.17 |
[백준] 23056 참가자 명단 - Java (0) | 2021.10.31 |
[백준] 10845 큐 - Java (0) | 2021.10.30 |
[백준] 2702 초6수학 - Java (0) | 2021.10.29 |
댓글
이 글 공유하기
다른 글
-
[백준] 1725 히스토그램 - Java
[백준] 1725 히스토그램 - Java
2021.11.17 -
[백준] 1016 제곱ㄴㄴ수 - Java
[백준] 1016 제곱ㄴㄴ수 - Java
2021.11.17 -
[백준] 23056 참가자 명단 - Java
[백준] 23056 참가자 명단 - Java
2021.10.31 -
[백준] 10845 큐 - Java
[백준] 10845 큐 - Java
2021.10.30