[백준] 빗물 (투 포인터)

문제 소개

빗물 - 백준 14719번 문제를 정리합니다.
이 문제는 벽 사이의 공간에 고이는 빗물의 양을 구하는 문제입니다.
핵심은 왼쪽과 오른쪽에서의 최대 높이를 기준으로 물이 고일 수 있는 높이를 판단하는 데 있습니다.

문제 링크: 빗물 - 백준 14719번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 왼쪽과 오른쪽에서 투포인터를 사용해 중앙으로 좁혀오며 탐색
2. 각 칸에서의 최대 빗물 높이는 좌우 벽 중 더 낮은 높이
3. 현재 칸의 높이와 비교하여 고일 수 있는 빗물 양을 누적

---

해결 과정 및 코드

핵심 아이디어

1. 양쪽 끝에서 출발하는 left, right 포인터 사용
   → leftMax, rightMax로 각 방향에서의 최대 벽 높이를 저장
2. leftMax < rightMax이면 왼쪽 기준으로 고일 수 있는 물을 계산
   → 현재 칸이 leftMax보다 낮으면 leftMax - 현재 높이만큼 물이 고임
   → 아니라면 leftMax를 갱신
3. 반대로 rightMax가 더 작거나 같으면 오른쪽 기준으로 계산
   → rightMax - 현재 높이만큼 고일 수 있는 물 양을 계산
4. 전체 루프를 통해 고인 물의 양을 누적

코드

시간 복잡도 : O(W)

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        int H = read(); // 세로 길이 (사용 안 함)
        int W = read(); // 가로 길이
        int[] map = new int[W];

        for (int i = 0; i < W; i++)
            map[i] = read(); // 각 위치에 쌓인 블록 높이

        int left = 0, right = W - 1;
        int leftMax = map[left++];     // 왼쪽 최대 벽 높이
        int rightMax = map[right--];   // 오른쪽 최대 벽 높이
        int rain = 0;

        // W < 3이면 고일 수 없음
        if (W < 3) {
            System.out.println(0);
            return;
        }

        while (left <= right) {
            if (leftMax < rightMax) {
                // 왼쪽 기준으로 물 계산
                if (map[left] < leftMax) {
                    rain += leftMax - map[left];
                } else {
                    leftMax = map[left];
                }
                left++;
            } else {
                // 오른쪽 기준으로 물 계산
                if (map[right] < rightMax) {
                    rain += rightMax - map[right];
                } else {
                    rightMax = map[right];
                }
                right--;
            }
        }

        System.out.println(rain);  // 총 고인 물 출력
    }

    public static int read() throws IOException {
        int cur, n = System.in.read() & 15;
        boolean isNegative = (n == 13);
        if (isNegative) n = System.in.read() & 15;
        while ((cur = System.in.read()) > 32) {
            n = (n << 3) + (n << 1) + (cur & 15);
        }
        return isNegative ? ~n + 1 : n;
    }
}