[백준]14179번. 빗물(JAVA)

https://www.acmicpc.net/problem/14719

---

문제

---

풀이

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int height = Integer.parseInt(st.nextToken());
        int length = Integer.parseInt(st.nextToken());
        int count = 0;

        int[] block = new int[length];
        int maxIdx = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < length; i++) {
            block[i] = Integer.parseInt(st.nextToken());
            if (block[i] > block[maxIdx]) {
                maxIdx = i;
            }
        }

        int leftIdx = 0;
        int rightIdx = length - 1;

        // Find leftIdx
        while (leftIdx < length && block[leftIdx] == 0) {
            leftIdx++;
        }

        // Find rightIdx
        while (rightIdx >= 0 && block[rightIdx] == 0) {
            rightIdx--;
        }

        int leftMax = block[leftIdx];
        int rightMax = block[rightIdx];

        for (int i = leftIdx + 1; i <= maxIdx; i++) {
            if (block[i] >= leftMax) {
                leftMax = block[i];
            } else {
                count += leftMax - block[i];
            }
        }

        for (int i = rightIdx - 1; i >= maxIdx; i--) {
            if (block[i] >= rightMax) {
                rightMax = block[i];
            } else {
                count += rightMax - block[i];
            }
        }

        System.out.println(count);
    }
}

 

처음엔 최대 인덱스를 기준으로 탐색을 진행하는 방향으로 문제를 풀어 문제의 예시에 있는 그림에서 대표적으로 인덱스 4에 걸려 답이 3이 나오는 문제가 발생했다.

 

문제를 해결하기 위해서는 왼쪽과 오른쪽 양쪽에서 다른 방식으로 진행하여 가운데 최대 인덱스를 향해가는 과정으로 문제를 풀어야 한다.