[JAVA]백준 14179번: 빗물

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

14719번: 빗물

1. 문제 설명

 

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 고이는 빗물의 총량은?

 

2. 풀이

 

어떤 경우에 빗물이 고일까?

 

세로를 기준으로 생각해보면 옆 left의 최대 높이, right의 최대 높이 중 최소 높이보다 현재 위치가 낮으면 그 차이만큼 빗물이 생긴다.

 

위의 사진에서 두번째 칸을 보자면, left의 최대 높이는 3이고 right의 최대 높이는 4이다. 최소 높이는 3이고 따라서 2만큼의 빗물이 세로로 생기게 된다.

 

가로를 기준으로 생각해보면 현재 높이보다 높거나 같은 것을 만날때마다 그 index의 차이만큼 빗물이 생긴다.

 

높이가 3인 경우를 생각해보자.

 

0번째 빗물과 3번째 빗물, 4번째 빗물이 높이가 3이상이다.

 

따라서 3번째 높이에 0번~ 3번까지, 3번~4번까지 물이 고이게 된다.

 

먼저, 가로로 접근하는 방법에 대해서 설명한 후 세로로 접근하는 방법에 대해서 설명하겠다.

 

1) 가로

 

가로로 접근하는 방법은 간단하다.

 

현재 높이 X보다 큰 높이를 가진 곳 B를 찾았을 경우 바로 전에 현재 높이 X보다 큰 높이를 가진 곳 A와의 거리를 구하면 된다.

 

이를 H부터 0까지 반복하면 되고 시간 복잡도는 O(HW)이다.

 

*로직

- 현재 높이 X보다 큰 높이를 가진 인덱스를 저장하기 위해 prev 변수 선언

- 처음에는 prev 변수에 -1 저장

- 현재 높이 X보다 큰 높이를 가졌을 때, prev 변수가 -1이면 prev 변수만 update 한다.

- 현재 높이 X보다 큰 높이를 가졌을 때, prev 변수가 -1이 아니라면 현재 위치와 prev 변수 사이의 길이를 answer에 저장, prev 변수를 update 한다.

- 높이 H부터 0까지 반복한다.

 

2) 세로

 

세로의 경우 현재 위치에서 왼쪽에서 높은 위치, 오른쪽에서 높은 위치를 구해야 한다.

 

따라서 0부터 W까지 이동하며 왼쪽에서 높은 위치를 구하고, W부터 0까지 이동하며 오른쪽에서 높은 위치를 구한다.

 

그 후 왼쪽의 높은 위치와 오른쪽 높은 위치 중 최솟값을 구한다.

 

그다음, 현재 위치와 최소 높이의 차이만큼 answer에 더해가면 된다.

 

시간 복잡도 : O(W)

 

 

 

 

3. 코드

1) 가로로 접근

// JAVA 11, 시간 156ms, 메모리 14388KB

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


public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int H, W;
        int[] rain;
        int answer = 0;

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

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        rain = new int[W];

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

        // 강수량 저장
        for (int x = 0; x < W; x++) {
            rain[x] = Integer.parseInt(st.nextToken());
        }

        for (int x = H; x >= 0; x--) {

            int prev = -1;

            // 현재 높이가 y보다 크다면 이전 prev 에서 y의 길이까지 더함
            // (가로로 더해간다.)
            for (int y = 0; y < W; y++) {
                if (rain[y] >= x) {
                    if (prev != -1) {
                        answer += y - prev - 1;
                    }
                    prev = y;
                }
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();

    }


}

2) 세로로 접근

// JAVA 11, 시간 136ms, 메모리 14292KB

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


public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int H, W;
        int[] rain;
        int[] left, right, min;
        int answer = 0;

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

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        rain = new int[W];
        left = new int[W];
        right = new int[W];
        min = new int[W];

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

        for (int x = 0; x < W; x++) {
            rain[x] = Integer.parseInt(st.nextToken());
        }

        int maxHeight = rain[0];

        for (int x = 0; x < W; x++) {
            if(maxHeight<rain[x])
                maxHeight = rain[x];
            left[x] = maxHeight;
        }

        maxHeight = rain[W - 1];

        for (int x = W-1; x >= 0; x--) {
            if(maxHeight<rain[x])
                maxHeight = rain[x];
            right[x] = maxHeight;
        }

        for (int x = 0; x < W; x++) {
            min[x] = Math.min(right[x], left[x]);

            if(min[x]>rain[x])
                answer += (min[x] - rain[x]);
        }

        bw.write(String.valueOf(answer));
        bw.flush();

    }


}