Q 14719 빗물

💡 문제 요약 및 분석

H,W 로 주어지는 2차원 세계에 블록이 쌓여있다. 비가 오면 빗물이 고인다. 고이는 빗물의 총량을 구하면 된다.

💡 알고리즘 설계

✅ 스택을 활용해서 가로막는 블록을 측정하면 될 것 같다.

1. 입력

   • 표준입력으로 이차원배열[H][W] 생성
   • 표준입력으로 블록의 위치에 1 입력

2. 연산

   • for문으로 배열을 한 행씩 반복한다.
   • 배열의 값이 1일 때, 스택에 값을 넣는다. (아무 값이나 상관없음) 이 때 sum 변수에 쌓인 값을 전역변수 total 에 반영한다.
   • 배열의 값이 0일 때, 스택을 확인한다. 스택에 값이 있으면 sum++, 값이 없으면 아무런 행동도 하지 않는다.
   • 행의 마지막 열이 0이면 그 전까지 쌓은 sum은 버린다. (total에 반영하지 않음)
   • 행의 마지막 열에 스택을 비운다.

3. 출력

   • total 변수를 출력한다.

💡 코드

import java.util.*;

public class Main {

    static int read() throws Exception {
        int c, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int H = read();
        int W = read();
        int[][] square = new int[H][W];
        for (int i = 0; i < W; i++) {
            int block = read();
            for (int j = H-1; j >= 0; j--) {
                if (block == 0) break;
                square[j][i] = 1;
                block--;
            }
        }

        int total = 0;
        for (int i = 0; i < H; i++) {
            Stack<String> stack = new Stack<>();
            int sum = 0;
            for (int j = 0; j < W; j++) {
                if (square[i][j] == 1) {
                    if (stack.contains("벽")) {
                        total += sum;
                        sum = 0;
                    }
                    stack.push("벽");
                } else {
                    if (stack.isEmpty()) continue;
                    sum++;
                }
            }
        }
        System.out.println(total);
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(H * W^2)	O(H * W)

💡 느낀점 및 기억할 정보

Stack

• push : 스택에 데이터 삽입
• pop : 스택에서 제일 위에 있는 데이터를 추출
• peek : 스택에서 제일 위에 있는 데이터를 확인 (추출하지 않고 확인만 한다)
• search(Element) : 해당 요소가 스택의 어디에 있는지 위치를 반환 (스택의 top = 1 이다). 요소가 없으면 -1 반환.
• isEmpty() : 스택이 비어있으면 true 반환
• contains(Element) : 스택에 E가 있으면 true 반환