[백준 14719번] 빗물

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

 

package implement;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Impl14719 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        List<Integer> block = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            block.add(Integer.parseInt(st.nextToken()));
        }

        int rainWater = getRainWater(M, block);

        System.out.println(rainWater);
    }

    private static int getRainWater(int M, List<Integer> block) {
        int current = 0;
        int leftMax = 0;
        int rightMax = 0;
        int rainWater =0;
        // 처음과 끝은 빗물이 고일수가 없음
        for (int i = 1; i < M - 1; i++) {
            current = block.get(i);
            leftMax = block.get(i);
            rightMax = block.get(i);

            for (int j = i - 1; j >= 0; j--) {
                if (block.get(j) > current) {
                    leftMax = Math.max(leftMax, block.get(j));
                }
            }

            for (int k = i + 1; k < M; k++) {
                if (block.get(k) > current) {
                    rightMax = Math.max(rightMax, block.get(k));
                }
            }

            if(Math.min(rightMax, leftMax) > current){
                rainWater +=(Math.min(rightMax,leftMax)-current);
            }
        }
        return rainWater;
    }
}

 

문제는 얼핏 보기에 간단해 보였지만, 실제로는 생각보다 복잡했습니다.

 

핵심 알고리즘은 배열의 두 번째 요소부터 마지막 바로 앞 요소까지 각각 확인하면서, 해당 요소의 왼쪽과 오른쪽에 있는 값들 쭉 비교해서 큰 값들을 찾습니다. 그리고 왼쪽 값  오른쪽 값  중 최소값을 선택하여 현재 요소의 값과의 차이를 계산하고, 이 차이값들을 모두 더하면 문제의 답을 얻을 수 있습니다.

 

아직 많은 부분에서 부족함을 느끼지만, 이러한 문제 풀이 과정을 통해 계속 성장해 나갈 수 있을 것입니다.