[백준] 6549번 히스트로그램에서 가장 큰 직사각형 / Java, Python
Baekjoon Online Judge
algorithm practice
- 단계별 문제풀기
20. 분할 정복
재귀를 응용하는 알고리즘, 분할 정복을 익혀 봅시다.
재귀를 응용하는 알고리즘, 분할 정복을 익혀 봅시다.
Java / Python
9. 히스토그램에서 가장 큰 직사각형
히스토그램에서 가장 큰 직사각형을 찾는 문제. 분할 정복으로도 풀 수 있고, 스택으로 풀 수도 있습니다.
이번 문제는 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하는 문제입니다.
- Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Stack;
class Main {
static int[] arr;
static int N;
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(), " ");
N = Integer.parseInt(st.nextToken());
if(N == 0)
break;
arr = new int[N];
for(int i=0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
System.out.println(getMax(0, N - 1));
}
}
private static long getMax(int left, int right){
if(left == right) return arr[left];
int mid = (left + right) / 2;
// 두 구간으로 나누어, 둘 중 큰 넓이를 반환
long ret = Math.max(getMax(left, mid), getMax(mid+1, right));
int start = mid;
int end = mid+1;
// mid 기준 양쪽으로 너비 2만큼 겹치는 직사각형
long height = (long)Math.min(arr[start], arr[end]);
ret = (long)Math.max(ret, height*2);
// 범위를 벗어나기 전까지 확장
while(left < start || end < right){
// 왼쪽 범위를 넘지 않은 경우
if(left < start && end < right){
// 높이가 높은 쪽으로
if(arr[start -1] < arr[end+1])
height = (long)Math.min(height, arr[++end]);
else
height = (long)Math.min(height, arr[--start]);
}
else if(left < start){
// 오른쪽 범위를 넘은 경우 왼쪽으로만
height = (long)Math.min(height, arr[--start]);
}
else if(end < right){
// 왼쪽 범위를 넘은 경우 오른쪽으로만
height = (long)Math.min(height, arr[++end]);
}
ret = Math.max(ret, height*(end-start+1));
}
return ret;
}
}
- Python
import sys
def getMax(l, r):
if l == r:
return h[l]
else:
mid = (l + r) // 2
start = mid
end = mid + 1
height = min(h[start], h[end])
tmp = height * 2
cnt = 2
while True:
if (h[start] == 0 or start == l) and (h[end] == 0 or end == r):
break
elif h[start] == 0 or start == l:
if h[end + 1] < height:
height = h[end + 1]
end += 1
elif h[end] == 0 or end == r:
if h[start - 1] < height:
height = h[start - 1]
start -= 1
else:
if h[start - 1] > h[end + 1]:
if h[start - 1] < height:
height = h[start - 1]
start -= 1
else:
if h[end + 1] < height:
height = h[end + 1]
end += 1
cnt += 1
tmp = max(tmp, height * cnt)
return(max(getMax(l, mid), getMax(mid + 1, r), tmp))
while True:
h = list(map(int, sys.stdin.readline().split()))
if h[0] == 0:
break
print(getMax(1, len(h) - 1))
Author And Source
이 문제에 관하여([백준] 6549번 히스트로그램에서 가장 큰 직사각형 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-6549번-히스트로그램에서-가장-큰-직사각형-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)