[구현] 백준 14719. 빗물

백준 14719. 빗물

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

일반적인 구현 문제였다. 2차원 세계의 벽의 높이가 주어졌을때, 그 사이에 고일수있는 빗물의 양을 구한다,

 

나는 2차원 배열로 벽을 그린 후, 0행부터 N-1행까지 행을 기준으로 돌면서 채울수있는 가로표면을 누적해가면서 풀었다.

하지만 어떤 아이디어를 통해 더 빠르게 구현하는 방법이 있는것을 깨달았다!

그래서 두가지 방법으로 풀어보았다. 1번이 내 첫 풀이, 2번이 더 효율적인 풀이이다.

 

풀이 1

1. map[][]에 벽을 저장한다

2. 행별로 탐색하면서 양옆이 막혔을때(즉, block이 2일때) 그 사이의 거리를 구해 저장한다.

 

즉, 위 그림에서 block이 두개일때인 index=3에서 이전 벽이 있던 index=0을 뺀 값이 거리인것이다.

 

cf)

공간복잡도 : map(O(h*w)) + 나머지변수는 상수 => O(H*W)

시간복잡도 : 입력처리(O(H*W)) + 물계산(O(H*W)) =>  O(H*W)

public class Main {
    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()); //가로 = 열
        int[][] map = new int[h][w];
        st = new StringTokenizer(br.readLine());

        for(int i=0; i<w; i++) { //열의 갯수만큼 반복
            //[0,1,2,3]일때 첫번째 열의높이 len=3이면, 3,2,1을 채운다.
            int len = Integer.parseInt(st.nextToken());
            for(int j=h-1; j>=h-len; j--) map[j][i] = 1;
        }

        int sum = 0;
        for(int i=0; i<h; i++) {
            int block = 0, preLocation = 0, water=0;
            for(int j=0; j<w; j++) {
                if(map[i][j] == 1) {
                    block++;
                    if(block == 2) {
                        water += (j-preLocation-1);
                        block--;
                    }
                    preLocation = j;
                }
            }
            sum += water;
        }

        System.out.println(sum);

    }
}

 

 

 

풀이 2

위 풀이 외에 많이 사용하는 풀이법은, 특정 위치에서 양옆을 탐색하면서 가장 높은벽을 찾고, 두 벽중 낮은값만큼 누적하는 방법이 있다. 그러나 이경우 매 위치에서 양옆을 매번 탐색해야하는 단점이 있는데, 이걸 다음과같이 해결 할 수 있다.

 

바로 왼쪽에서 오른쪽으로 한번, 오른쪽에서 왼쪽으로 한번 지나가면서 최대높이를 갱신해두는것이다.

 

위 상태에서 왼->오로 순회하며 특정벽의 왼쪽중 가장 큰 벽을 저장한다.

벽 높이 : [3,1,2,3,4,1,1,2]

왼쪽벽 최대높이 : [3,3,3,3,4,4,4,4]

 

반대로 오->왼으로 순회하면

벽 높이 : [3,1,2,3,4,1,1,2]

오른쪽벽 최대높이 : [4,4,4,4,4,2,2,2]

 

빗물높이는 왼쪽벽 최대높이와 오른쪽벽 최대높이중 더 작은것을 선택한다. 

빗물높이 : [3,3,3,3,4,2,2,2] 

 

이후 각 위치에서 빗물높이-벽높이를 한 후 결과에 더해준다.

 

cf)

공간복잡도 : block배열(W) + rain배열(W) = O(W)

시간복잡도 : O(W) + O(W) => O(W)

 

public class Main {

    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());

        int[] blocks = new int[W];
        int[] rain = new int[W];
        st = new StringTokenizer(br.readLine());

        //왼쪽 벽
        int height = 0;
        for (int i = 0; i < W; i++) {
            blocks[i] = Integer.parseInt(st.nextToken());
            height = Math.max(height, blocks[i]);
            rain[i] = height;
        }
       
        //오른쪽 벽 최댓값와 왼쪽벽 최댓값중 작은것
        height = 0;
        int ans = 0;
        for (int i = W - 1; i >= 0; i--) {
            height = Math.max(height, blocks[i]);
            rain[i] = Math.min(height, rain[i]);
            ans += rain[i] - blocks[i];
        }

        System.out.println(ans);
    }
}