백준 14719번 : 빗물 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

빗물 골드 5

 

📖 문제

 

좀 헤맸던 문제다. 

높이가 같거나 큰 것 중 작은 거를 기준으로 빗물을 담으면 되는데

뭐를 기준으로 할 지가 문제였고, 

높이가 줄어드는 형태에서도 문제였다.

예제의 4 1 1 2 이 줄어드는 형태다.

 

각 블록을 기준으로

왼쪽 오른쪽으로 같거나 큰 것을 찾는 거로 할려다가 중복 문제가 있어서 깔끔하게 버리고

 

왼쪽에서부터 기준을 잡고 오른쪽 포인터를 움직이면서

왼쪽 포인터의 실제 값보다 작으면 스택에 담아두고 

오른쪽 포인터의 실제값이 왼쪽보다 크거나 같으면  왼쪽 값과 오른쪽 값중 더 작은 것을 min값으로 설정하고

스택에 넣었던 작은 블록들을 꺼내서 min - stack.pop() 한 값을 answer에 누적합한다. 

 

문제는 높이가 줄어드는 형태인데

이 경우 스택을 이용했으므로 쉽게 풀린다. 

4 1 1 2 의 경우 스택에는 (top)2 1 1로 쌓였을 것이다. 

 

때문에 꺼내서 다시 배열로 만들면 2 1 1 이 되고 마지막에 left의 값을 넣어주면 2 1 1 4 로 위의 로직을 다시한 번 할 수 있다. 

 

 

GPT 정리

각 블록을 기준으로 왼쪽과 오른쪽에서 자신보다 크거나 같은 블록을 찾는 방식으로 접근할 수도 있었지만, 그렇게 하면 중복 계산이 발생할 수 있어서 깔끔하게 버리고 왼쪽에서부터 기준을 잡고 오른쪽 포인터를 움직이는 방식으로 탐색을 진행했다.

 

우선 왼쪽 포인터(left)를 기준으로 잡고, 오른쪽 포인터(right)를 하나씩 이동하면서 right 위치의 블록이 left보다 작으면 스택에 담아두고, left보다 크거나 같아지는 순간이 오면 left와 right 중 작은 값을 min으로 설정한 뒤, 스택에서 블록들을 꺼내 min - stack.pop()을 answer에 누적합했다. 이 과정을 반복하면서 빗물이 고일 수 있는 공간을 계산했다.

 

문제는 높이가 줄어드는 형태일 때 발생하는데,

이 경우에도 스택을 활용하면 쉽게 해결할 수 있다. 예를 들어 4 1 1 2 같은 경우를 보면,

stack에는 (top) 2 1 1 순서로 쌓이게 된다. 여기서 이 블록들을 다시 배열로 만들면 2 1 1이 되고, 마지막에 left 값을 추가하여 2 1 1 4로 변환하면, 동일한 탐색 로직을 한 번 더 적용할 수 있다.

이렇게 하면 한 번의 탐색으로 해결되지 않는 경우를 처리할 수 있다.

 

즉, 한 방향(왼쪽 → 오른쪽)으로 탐색하면서 스택을 활용해 중복 없이 처리하고, 남은 블록들은 다시 배열로 변환해서 한 번 더 탐색하는 방식으로 해결한 것이다.

---

🔅 문제 풀이

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

public class Main {
    static int answer = 0;

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

        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 = leftSearch(blocks, stack);

        // 남은 것은 마지막 left위치의 블록 높이보다 작은 블록들이다.
        // 해당 블록들을 꺼내서 다시 배열에 넣는다.
        // 이때 왼쪽 <= 오른쪽 블록 배열이 될 것이다.
        int[] restBlocks = new int[stack.size() + 1];
        int idx = 0;

        while (!stack.isEmpty()) {
            restBlocks[idx++] = stack.pop();
        }

        restBlocks[idx] = blocks[left]; // 가장 큰 값인 left를 마지막에 넣어준다.
        leftSearch(restBlocks, stack);

        bw.write(answer+ "");
        bw.flush();
        bw.close();

    }

    // 왼쪽 <= 오른쪽인 블록들을 기준으로 탐색
    private static int leftSearch(int[] blocks, Stack<Integer> stack) {
        int left = 0, right = 1;

        while (right < blocks.length) {
            if (blocks[left] <= blocks[right]) { // 왼쪽 기준 블록보다 오른쪽 블록이 크거나 같다면

                int min = Math.min(blocks[left], blocks[right]); // 둘중 최솟값을 구하고
                while (!stack.isEmpty()) {
                    answer += min - stack.pop(); // 최솟값 - 범위 안 높이들을 빼서 물이 고인 높이를 구한다.
                }
                left = right; // left~right 안 범위는 다 구했으므로 left를 right로 이동
                right++; // right도 한 칸 이동

            } else {
                stack.push(blocks[right++]); // left보다 작으므로 stack에 넣어준다.
            }
        }

        return left; // 남은 블록들 계산을 위해 left를 넘긴다.
    }


}

 

 

 

❗ 오답노트 / 필요한 지식

1. 다른 사람은 최대 높이값을 찾아서 그 블록을 기준으로 오른쪽 왼쪽 탐색을 했다. 
2. 탐색 방향은 (왼쪽에서 최대높이까지)  -> 최대높이 <-  (오른쪽에서 최대높이까지)