[백준] 14719번 : 빗물 (Java)

🔗 14719번 : 빗물
● Java 풀이
● 시간 제한 1초
● 메모리 제한 256 MB

✅ 문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

---

✅ 테스트 케이스

// input
4 8
3 0 1 2 1 2 3 4

//answer
9

// input
500 3
1 2 500

// answer
0

// input
500 5
500 2 1 1 2

//answer
2

// input
500 4
0 2 1 500

// answer
1

// input
500 3
500 2 500

// answer
498

// input
500 500
500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1 500 1

// answer
124251

// input
3 6
5 4 1 3 1 2

// answer
3

---

✅ 풀이

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());
        st.nextToken();  // 블록의 최대 높이
        int W = Integer.parseInt(st.nextToken());  // 블록 정렬 개수 (너비)

        st = new StringTokenizer(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();  // 높이를 비교할 Priority Queue 생성

        int blockHeight, maxHeight = 0;  // 현재 확인할 블록 높이, 지금까지 찾은 블록 중 최대 높이
        int count = 0;  // 지금까지 채운 물의 칸 수
        for (int i = 0; i < W; i++) {
            blockHeight = Integer.parseInt(st.nextToken());  // 다음 블록 높이 받기
            if (maxHeight <= blockHeight) {  // 현재 블록이 최대 높이와 같거나 최대 높이보다 클 경우
                while (!pq.isEmpty() && pq.peek() <= maxHeight) {  // 지금까지의 낮은 높이들을
                    count += maxHeight - pq.poll();  // 이전의 최대 높이만큼 채우기
                }
                maxHeight = blockHeight;  // 최대 높이를 현재 블록 높이로 변경 (이전 블록은 다시 돌아보지 않음)
            } else {  // 현재 블록이 최대 높이보다 낮을 경우
                while (!pq.isEmpty() && pq.peek() < blockHeight) {  // 현재 높이보다 낮은 높이가 있을 때
                    count += blockHeight - pq.poll();  // 블록 높이를 현재 높이로 채우기
                    pq.add(blockHeight);  // 물 더하기
                }
            }
            pq.add(blockHeight);  // 현재 블록 삽입
        }

        System.out.println(count);
    }
}

 

이 문제는 최대 높이가 나왔을 경우, 이전의 블록들을 더이상 돌아볼 필요가 없다는 것을 기억해야 한다.

탐색한 최대 높이보다 더 큰 높이가 나왔을 경우 그 이전 블록들은 물이 더이상 채워질 수 없기 때문이다.

블록이 이와 같이 주어졌을 때, 2 높이 블록의 높이를 받을 때의 Priority Queue 는 {1, 3}이다.

2 높이 블록은 최대 높이인 3 높이 블록보다 낮으므로, Priority Queue에서 자신보다 낮은 수가 존재하지 않을 때까지 물을 채우고 끝낸다. {2, 2, 3}

 

하지만 최대 높이인 3 높이보다 높은 블록이 나타났을 경우는 어떨까?

이후 나타난 3 높이 블록은 최대 높이인 3 높이 블록과 같으므로, Priority Queue에서 이전 최대 높이보다 낮은 수가 존재하지 않을 때까지 물을 채우되, 물을 채운 블록들은 더이상 신경쓰지 않는다.

 

그 이유는 아래에 제시한 그림과 같다.

이후 블록이 어떤 높이가 와도, 마지막 최대 높이 이전의 블록에 채울 수 있는 물은 그 공간 내에 최대 높이를 넘을 수 없기 때문이다. 중간의 3 높이 블록이 4 높이로 바뀌었다고 가정해보자. 그럼에도 그 공간 내에 채울 수 있는 물은 이전 최대 높이인 첫 번째 블록, 3 높이인 것은 마찬가지이다.

 

이를 고려하며 문제를 풀면 반복 횟수를 줄일 수 있다.