[Baekjoon-14719] 빗물

문제

[Baekjoon-14719] 빗물

---

문제 해결 아이디어

우선순위 큐를 활용해서 2차원 세계의 벽 높이를 오름차순으로 정렬 후 순서대로 물 채우기🪣

조건

• 직관적으로 벽 사이에 물이 고임
• 2차원 세계의 바닥은 막혀있음 (0이 마지막)

PriorityQueue 접근

• Block 객체를 생성하여 i index, h height 저장
• PriorityQueue에 h 내림차순으로 정렬 (높은 벽 먼저)
• b1, b2 높은 벽과 그 다음 높은 벽 꺼내서 반복

빗물 채우기

b1부터 b2사이에 index에 위치한 세계에 b2 높이 만큼 빗물 채우기

for (int i = l + 1; i < r; i++) {
    int water = b2.h - world[i];
    if (water > 0) {
    	ans += water;
        world[i] = b2.h;
    }
}

---

코드

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

public class Solution14719 {
    static int H, W;
    static int[] world;
    static int ans;
    static PriorityQueue<Block> pq;

    static class Block {
        int i;
        int h;

        Block(int i, int h) {
            this.i = i;
            this.h = h;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        world = new int[W];
        ans = 0;
        pq = new PriorityQueue<>(Comparator.comparingInt((Block b) -> b.h).reversed());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < W; i++) {
            world[i] = Integer.parseInt(st.nextToken());
            pq.offer(new Block(i, world[i]));
        }
        
        while (pq.size() > 1) {
            Block b1 = pq.poll();
            Block b2 = pq.peek();
        
            int l = Math.min(b1.i, b2.i);
            int r = Math.max(b1.i, b2.i);
        
            for (int i = l + 1; i < r; i++) {
                int water = b2.h - world[i];
                if (water > 0) {
                    ans += water;
                    world[i] = b2.h;
                }
            }
        }
        System.out.println(ans);
    }
}