🥇 [Baekjoon / Java] 14719. 빗물

문제 설명

💡 Info

• 난이도 : 골드 V
• 시간 제한 : 1초
• 메모리 제한 : 256MB
• 백준 링크: https://www.acmicpc.net/problem/14719
• 풀이 링크(GitHub): hayannn/CodingTest_Java/백준/Gold/14719. 빗물

내용

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

📥입력 조건

• 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)
• 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.
• 따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

📤출력 조건

• 2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.
• 빗물이 전혀 고이지 않을 경우 0을 출력하여라.

입출력 예시

• 입력 1

  4 4
  3 0 1 4

• 출력 1

  5

• 입력 2

  4 8
  3 1 2 3 4 1 1 2

• 출력 2

  5

• 입력 3

  3 5
  0 0 0 2 0

• 출력 3

  0

문제 이해

• 높이(세로)인 H와 너비(가로)인 W를 입력받아서, 최솟값이 존재하지 않도록 채우기!

알고리즘

실제 풀이 시간 : 30분

• 입력
  • 높이(세로)인 H와 너비(가로)인 W를 입력받기
  • 블록 높이들을 보여주는 배열 입력받기
• 계산
  • i를 기준으로 i-1에 있는 개수와 i+1에 있는 개수를 비교
    • 그 중 더 작은 수에서 i를 빼서 계산
    • 그렇게 얻은 i는 모두 합하기
• 출력
  • i의 합 출력하기

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
			
			int H = sc.nextInt();
			int W = sc.nextInt();
			
			int[] arr = new int[W];
			for(int i=0; i<W; i++) {
				arr[i] = sc.nextInt();
			}
			
			int resultOne = 0;
			int resultTwo = 0;
			
			for(int i=1; i<W-1; i++) {
				if(arr[i-1] > arr[i+1]) {
					resultOne = arr[i+1] - arr[i];
				}
				if(arr[i-1] < arr[i+1]) {
					resultTwo = arr[i-1] - arr[i];
				}
			}
			System.out.print(resultOne + resultTwo);
	}
}

오답 체크

• 결과가 다르게 나오는 문제
  • 비교를 i를 기준으로 그 앞의 i-1, 그 뒤의 i+1 하던 방식에서
  • → Math.min을 이용해 i를 기준으로 왼쪽에 있는 높이 중 최대 높이와, i를 기준으로 오른쪽에 있는 높이 중 최대 높이를 비교해서 더 작은 값을 찾는 방식으로 변경!
• 또한, maxH라는 별도 메서드를 만들어 가장 큰 값을 찾는 부분을 분리!

//before
int resultOne = 0;
			int resultTwo = 0;
			
			for(int i=1; i<W-1; i++) {
				if(arr[i-1] > arr[i+1]) {
					resultOne = arr[i+1] - arr[i];
				}
				if(arr[i-1] < arr[i+1]) {
					resultTwo = arr[i-1] - arr[i];
				}
			}
			System.out.print(resultOne + resultTwo);
		}
	}

//after
			int result = 0;
			
			for(int i = 1; i < W - 1; i++) {
	            int minH = Math.min(maxH(arr, 0, i), maxH(arr, i + 1, W)); //i를 기준으로 왼쪽에 있는 높이 중 최대 높이 | 오른쪽에 있는 높이 중 최대 높이를 비교 -> 더 작은 수 찾기
	            if(arr[i] < minH) { // 현재 위치의 값이 최솟값보다 작을 때
	                result += minH - arr[i]; // 빗물의 양 계산하여 결과에 더함
	            }
	        }
	        System.out.print(result);
	    }
	    
	    // 주어진 범위에서 최대 높이를 찾는 함수
	    static int maxH(int[] arr, int start, int end) {
	        int max = 0;
	        for(int i = start; i < end; i++) {
	            max = Math.max(max, arr[i]);
	        }
	        return max;
	    }
	}

최종 풀이

실제 풀이 시간 : 46분(첫 풀이 포함)

• 입력
  • 높이(세로)인 H와 너비(가로)인 W를 입력받기
  • 블록 높이들을 보여주는 배열 입력받기
• 계산
  • i를 기준으로 왼쪽에 있는 높이 중 최대 높이 | 오른쪽에 있는 높이 중 최대 높이를 비교
    • 그 중 더 작은 수에서 i를 빼서 계산
    • 그렇게 얻은 i는 모두 합하기
• 출력
  • i의 합 출력하기

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
			
		int H = sc.nextInt();
		int W = sc.nextInt();
		
		int[] arr = new int[W];
		for(int i=0; i<W; i++) {
			arr[i] = sc.nextInt();
		}
		
		int result = 0;
		
		for(int i = 1; i < W - 1; i++) {
            int minH = Math.min(maxH(arr, 0, i), maxH(arr, i + 1, W)); //i를 기준으로 왼쪽에 있는 높이 중 최대 높이 | 오른쪽에 있는 높이 중 최대 높이를 비교 -> 더 작은 수 찾기
            if(arr[i] < minH) { // 현재 위치의 값이 최솟값보다 작을 때
                result += minH - arr[i]; // 빗물의 양 계산하여 결과에 더함
            }
        }
        System.out.print(result);
    }
    
    // 주어진 범위에서 최대 높이를 찾는 함수
    static int maxH(int[] arr, int start, int end) {
        int max = 0;
        for(int i = start; i < end; i++) {
            max = Math.max(max, arr[i]);
        }
        return max;
    }
}