public class FloodDepth_230123{
public static void main(String[] args) {
int [] A = {1,3,2,1,2,1,5,3,3,4,2};
System.out.println(solution(A));
}
/*
당신은 산악 호수가 있는 지역을 조사하는 지질학자 친구를 돕고 있습니다.
최근 폭우로 인해 이 호수가 범람했으며 수위가 최고점에 도달했습니다.
당신의 친구는 이 호수의 가장 깊은 부분의 최대 깊이를 알고 싶어합니다.
문제를 2차원 차원으로 단순화합니다.
전체 풍경은 작은 블록으로 나눌 수 있으며 길이 N의 배열 A로 설명할 수 있습니다.
A의 각 요소는 블록의 암석 바닥의 고도(즉, 물이 전혀 없을 때 이 블록의 높이)입니다.
강우 후 모든 저지대(즉, 양쪽에 더 높은 블록이 있는 블록)는 가능한 한 많은 물을 보유하고 있습니다.
이 전체 지역이 침수된 후 최대 수심을 알고 싶습니다.
이 영역 외부의 고도는 0이고 외부 영역은 무한한 양의 물을 수용할 수 있다고 가정할 수 있습니다.
예를 들어 다음과 같은 어레이 A를 고려하십시오.
A[0] = 1
A[1] = 3
A[2] = 2
A[3] = 1
A[4] = 2
A[5] = 1
A[6] = 5
A[7] = 3
A[8] = 3
A[9] = 4
A[10] = 2
다음 그림은 홍수가 난 후의 풍경을 보여줍니다.
회색 영역은 위의 배열 A로 설명된 암석 바닥이고
점선이 있는 파란색 영역은 가능한 최대 볼륨으로 저지대 영역을 채우는 물을 나타냅니다.
따라서 3,5블럭은 수심이 2이고, 2,4,7,8블럭은 수심이 1이므로 이 지역의 최대 수심은 2이다.
함수 작성:
class Solution { public int solution(int[] A); }
N개의 정수로 구성된 비어 있지 않은 배열 A가 주어지면 최대 수심을 반환합니다.
위에 표시된 배열 A가 주어지면 함수는 위에서 설명한 대로 2를 반환해야 합니다.
다음 어레이의 경우:
A[0] = 5
A[1] = 8
이 풍경은 물을 담을 수 없기 때문에 함수는 0을 반환해야 합니다.
다음 가정에 대한 효율적인 알고리즘을 작성 하십시오.
N은 범위 [ 1 .. 100,000 ] 내의 정수 이고;
배열 A의 각 요소는 [ 1 .. 100,000,000 ] 범위 내의 정수 입니다.
*/
public static int solution(int[] A) {
int 물깊이 = 0;
int 최대높이 = A[0];
int 바닥높이 = A[0];
for (int i = 1; i < A.length; i++) {
if (A[i - 1] < A[i]) {
if (A[i] <= 최대높이) {
if (물깊이 < A[i] - 바닥높이){
물깊이 = A[i] - 바닥높이;
System.out.println("\t물깊이1 " + 물깊이);
}
} else {
if (물깊이 < 최대높이 - 바닥높이){
물깊이 = 최대높이 - 바닥높이;
System.out.println("\t물깊이2 " + 물깊이);
}
최대높이 = A[i];
바닥높이 = A[i];
}
} else {
if (A[i] < 바닥높이){
바닥높이 = A[i];
System.out.println(i + " 바닥높이 " + 바닥높이);
}
}
}
return 물깊이;
}
public static int solution_test(int[] A) {
int 물깊이 = 0;
int 물최대높이 = 0;
for(int i = 0; i < A.length; i++){
물최대높이 = Math.max(물최대높이,A[i]);
if(물최대높이 > A[i] && i != 0 && i != A.length-1){
물깊이 = Math.max(물최대높이 - A[i], 물깊이);
//System.out.println(물최대높이 + "ㅇㅅㅇ " + 최대물높이);
}
}
return 물깊이;
}
}
댓글
댓글 쓰기