백준 14719 빗물 (JAVA)

문제

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

14719번: 빗물

풀이1

처음에는 코드1과도 같이 풀었다. 처음에는 브루트 포스처럼 풀었다. 배열역시 2차원으로 형성하고 2차원을 각각 빈공간, 건물이 있는 공간, 물로 차있는 공간 이렇게 하나씩 전부 매핑하면서 풀었다. 그러나 이러한 방식은 for문을 4개나 요구하였고 결국 (물론 풀이는 맞았지만) 시간복잡도에서 최악의 결과를 가져왔다.

시간 복잡도가 2000ms가 넘어가는 것을 확인할 수 있다.

그렇기에 나는 다른 방식에 대해서 검색을 해보았고 그 결과 2차원으로 배열을 만들어 주어서 풀이를 진행하는 것이 아니라 하나씩 1차원으로도 충분히 답을 구할수 있다는 것, 그리고 사이에 고이는 빗물을 한번에 해결하는 것이 아닌 하나씩 해도 충분히 답을 구할 수 있다는 것을 알게되었다.

추가로 풀이1 의 방식은 1기준 빌딩을 잡고 오른쪽으로 가면서 기준점보다 같거나 높은 빌딩을 찾는다. 그리고 그 사이에 빗물이 찰 수 있는 공간을 찾아서 빗물을 채워넣는 방식이다.

 

코드1

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

public class Main{

    static int H, W;
    static int[][] world;
    static int[] height;

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

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

        world = new int[H+2][W+2];
        height = new int[W+2];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= W; i++) {
            height[i] = Integer.parseInt(st.nextToken());
        }

        //world 생성
        for (int i = 1; i <= W; i++) {
            for (int j = 0; j < height[i]; j++) {
                world[H - j][i] = 1;
            }
        }

        for (int i = 1; i <= W; i++) { //왼쪽 기준
            for (int j = i+1; j <= W; j++) {  //오른쪽 기준
                fill(i, j);
            }
        }

        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                if(world[i][j] == 2)
                    ans++;
            }
        }
        System.out.println(ans);
    }

    private static void fill(int i, int j) {
        int h = Math.min(height[i], height[j]);

        for (int m = i + 1; m < j; m++) {
            for (int n = H; n > H - h; n--) {
                if(world[n][m] == 0)
                    world[n][m] = 2;
            }
        }
    }
}

 

풀이2

풀이1의 방식이 아닌 1차원의 배열로 문제를 해결한 풀이이다. 코드 역시 훨씬 더 깔끔하며 직관적이다.

풀이 방식은 기준점을 하나 잡고 해당 기준점을 기준으로 왼쪽과 오른쪽에서 각각 제일 높은 건물의 높이를 구한다. 그리고 두개의 값중 작은 값을 구하고 해당 값에서 현재 건물의 높이값을 빼주어서 현재 빌딩위에 쌓일 수 있는 빗물의 높이만을 구해준다.(풀이1의 경우에는 한번에 전부 구하는 방식이었다면 풀이2는 하나씩 차례대로) 그 결과 메모리 사용량은 아주 조금 늘었지만 답을 구하는데 있어서 시간이 확실하게 줄었다.

줄어든 시간복잡도를 확인할 수 있다.

코드2

package com.company;

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

public class Main{

    static int[] map;
    static int ret, left, right;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        map = new int[W];
        ret = left = right = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < W; i++) {
            map[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i < W-1; i++) {
            left = right = 0;

            for (int j = 0; j < i; j++) {
                left = Math.max(left, map[j]);
            }

            for (int j = i + 1; j < W; j++) {
                right = Math.max(right, map[j]);
            }

            if(map[i] < left && map[i] < right){
                ret += Math.min(left, right) - map[i];
            }
        }

        System.out.println(ret);
    }
};