[백준] 14719번 : 빗물 - 자바[Java]

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

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 = new StringTokenizer(br.readLine());
        
    	int h = Integer.parseInt(st.nextToken());
    	int w = Integer.parseInt(st.nextToken());
    	int[] blocks = new int[w];
    	
    	// 블록 입력
    	st = new StringTokenizer(br.readLine());
    	for (int i = 0; i < w; i++) {
    		blocks[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	// 맨 왼쪽의 블력 저장
    	int left = blocks[0];
    	int leftIdx = 0;
    	int cnt = 0;
    	
    	// 2번째 블록부터 탐색 시작
    	for (int idx = 1; idx < w; idx++) {
    		int block = blocks[idx];
    		
    		// 현재 블록이 맨 왼쪽의 블럭보다 높거나 같은 경우, 현재 블록이 마지막 블록인 경우
    		// 그 부분만 짤라서 그 부분에서 고이는 빗물의 총량을 구한다.
    		if (block >= left || idx == w-1) {
    			int[] part = Arrays.copyOfRange(blocks, leftIdx, idx+1);
    			cnt += countRain(part);
    			left = block;
    			leftIdx = idx;
    		}
    	}
    	
    	System.out.println(cnt);
    	
    }
    
    private static int countRain(int[] part) {
    	int len = part.length;
    	int left = part[0];
    	int right = part[len-1];
    	int cnt = 0;
    	
    	// 맨 왼쪽 블록과 맨 오른쪽 블록과의 높이 차를 구해 그 중 최솟값을 cnt에 더한다.
    	for (int i = 1; i < len - 1; i++) {
    		int block = part[i];
    		cnt += Integer.min(left - block, right - block);
    	}
    	
    	return cnt;
    }
    
    
}

하지만 위 풀이는 틀린 풀이었고, 위 풀이에 대한 반례를 찾을 수 있었다.

4 8
0 1 0 1 4 1 2 1

{4, 1, 2} 이 부분에서 고이는 빗물이 발생하는데, 위 풀이로는 {4, 1, 2}를 잡아내지 못하고 {4, 1, 2, 1} 부분에 대해 countRain()을 호출해 오답을 냈다.

 

이러한 오답을 해결하기 위해 다른 풀이 방식을 생각해야했고, 아래와 같이 풀이하였다.

전체 코드

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 = new StringTokenizer(br.readLine());
        
    	int h = Integer.parseInt(st.nextToken());
    	int w = Integer.parseInt(st.nextToken());
    	int[] blocks = new int[w];
    	
    	// 블록 입력
    	st = new StringTokenizer(br.readLine());
    	for (int i = 0; i < w; i++) {
    		blocks[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	System.out.println(countRain(blocks));
    	
    }
    
    private static int countRain(int[] blocks) {
    	// 고이는 빗물의 총량
    	int cnt = 0;
    	
    	// 양쪽 끝에 있는 블력을 제외한 각 블럭들을 순차적으로 탐색
    	for (int i = 1; i < blocks.length - 1; i++) {
    		int block = blocks[i];
    		
    		// 현재 블력의 왼쪽에 있는 블럭들 중 가장 큰 블럭과 블럭의 오른쪽에 있는 블럭들 중 가장 큰 블럭을 구한다.
    		int[] left = Arrays.copyOfRange(blocks, 0, i);
    		int[] right = Arrays.copyOfRange(blocks, i + 1, blocks.length);
    		int leftMax = Arrays.stream(left).max().getAsInt();
    		int rightMax = Arrays.stream(right).max().getAsInt();
    		
    		// 현재 블럭이 그 두 블럭보다 작은 경우, 그 블럭들과의 차이 중 최솟값을 cnt에 더한다.
    		if (block < leftMax && block < rightMax) {
    			cnt += Integer.min(leftMax - block, rightMax - block);
    		}
    	}
    	
    	return cnt;
    }
}

현재 블력의 왼쪽에 있는 블럭들 중 가장 큰 블럭과 블럭의 오른쪽에 있는 블럭들 중 가장 큰 블럭을 구할 때는 Stream을 사용하여 구했다.

 

Reference

자바 배열의 깊은 복사, 얕은 복사

[Java] 자바 배열을 복사하는 다양한 방법 (깊은복사, 얕은복사)

 

다른 풀이

https://www.acmicpc.net/source/65027962

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

/*
 * 1. summary: 문제 해석
 * 주어진 블록에서 빗물이 채워지는 곳의 값을 구하라
 *
 * 2. strategy: 해결 전략
 * - 왼쪽에서 오른쪽으로 점점 더 커지는 높이의 값들을 기록
 * - 오른쪽에서 왼쪽으로 점점 더 커지는 높이의 값들을 기록
 * - 둘 중 더 낮은 값을 찾아서 (= 물이 고일 수 있는 높이) 현재 높이와의 차를 더한다.
 *
 * 3. note:
 * */
public class Main {

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

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

        int[] heights = new int[W];

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

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

        int result = 0;
        int last = W-1;
        int left = heights[0];
        int right = heights[last];
        int[] lefts = new int[W];
        int[] rights = new int[W];

        for (int i = 1; i < last; i++) {
            if (left <= heights[i]) left = heights[i];
            if (right <= heights[last-i]) right = heights[last-i];
            lefts[i] = left;
            rights[last-i] = right;
        }

        for (int i = 1; i < last; i++) {
            int minHeight = Math.min(lefts[i], rights[i]);
            result += minHeight - heights[i];
        }

        wr.write(result + " ");
        wr.flush();
        wr.close();
    }
}

blocks 3 1 2 3 4 1 1 2
lefts        3 3 3 4 4 4
rights      4 4 4 4 2 2

sum = 2 + 1 + 1 + 1 = 4