[BOJ] 빗물 - JAVA

- 링크 : https://www.acmicpc.net/problem/14719

14719번: 빗물

 

- 풀이

  1. 시작을 기준으로 시작부터 이동하면서 다음 블록의 높이가 더 높아지는 것을 찾는다. (왼 -> 오)

  2. 찾으면서 더 낮은 블록이나 없는 블록들은 차를 합산 해 둔다.

  3. 더 높아진 것을 찾으면 합산 해 둔 값을 answer에 더한다.

  4. 끝까지 이동했다면 가장 높은 점 idx를 기록 해 둔다.

      ( 왼 -> 오, 오 -> 왼 할 때 같은 높이의 기둥이 2개면 두 번 계산하기 때문)

  5. 끝을 기준으로 가장 높은 점 idx 까지 이동하면서 이전 블록의 높이가 높아지는 것을 찾는다. (오 -> 왼)

  6. 2, 3번 반복

  7. answer 값을 도출한다.

 

 - 답

import java.util.*;

public class Solution {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int[] blocks = new int[w];
        for (int i = 0; i < w; i++) {
            blocks[i] = sc.nextInt();
        }

        int answer = 0;
        int topHeight = blocks[0];
        int sum = 0;
        int lastHeightIdx = 0;
        for (int i = 1; i < blocks.length; i++) {
            int currentHeight = blocks[i];
            if (topHeight > currentHeight) {
                sum += topHeight - currentHeight;
            } else {
                answer += sum;
                topHeight = currentHeight;
                sum = 0;
                lastHeightIdx = i;
            }
        }

        topHeight = blocks[blocks.length-1];
        sum = 0;
        for (int i = blocks.length-2; i >= lastHeightIdx; i--) {
            int currentHeight = blocks[i];
            if (topHeight > currentHeight) {
                sum += topHeight - currentHeight;
            } else {
                answer += sum;
                topHeight = currentHeight;
                sum = 0;
            }
        }

        System.out.println(answer);

    }
}