14719번 - stack 응용

비록 골드 5티어지만 드디어 골드까지 왔다.

14719번: 빗물 (acmicpc.net)

위 문제를 풀게 되었다.

간단히 설명하자면 2차원 세계가 주어지고, 그곳에 비가와서 비가 고인다는 내용이다.

위와 같이 고이게 되고 빗물이 얼만큼 고였는지 출력해줘야 한다.

입력으로는 2차원 세계의 크기와 각 칸마다 높이가 어느정도인지 주어진다.

나는 한칸씩 전진하며 만약 뒤의 블럭이 지금 블럭보다 낮고,
그 뒤에서 가장 높은 블럭이 지금 블럭보다 높은지 낮은지를 판단하여
만약 낮다면 채우지 않고, 낮지 않다면 물을 채워주는 방식으로 풀었다.

 

전체 코드

import java.util.*;

public class 빗물_14719번 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int H = sc.nextInt();
        int W = sc.nextInt();
        int[] wList = new int[W];

        for (int i = 0; i < W; i++) {
            wList[i] = sc.nextInt();
        }

        int maxLeft = 0;
        int sum = 0;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < W; i++) {
            int num = wList[i];
            int min = Math.min(maxLeft , num);
            maxLeft = Math.max(maxLeft , num);
            int count = 0;
            while (!stack.isEmpty() && stack.peek() < min) {
                sum += min - stack.pop();
                count++;
            }
            for (int j = 0; j < count; j++) {
                stack.add(num);
            }
            stack.add(num);
        }

        System.out.println(sum);
    }
}

 

만약 다음 그림처럼 입력을 받았다고 생각해보자
입력은 3 1 2 3 4 1 1 2 이다.

해당 과정은 다음 반복문에서 이뤄진다.

for (int i = 0; i < W; i++) {
    int num = wList[i];
    int min = Math.min(maxLeft , num);
    maxLeft = Math.max(maxLeft , num);
    int count = 0;
    while (!stack.isEmpty() && stack.peek() < min) {
        sum += min - stack.pop();
        count++;
    }
    for (int j = 0; j < count; j++) {
        stack.add(num);
    }
    stack.add(num);
}

현 위치에는 라이언을 올려 설명하겠다. maxLeft와 sum은 0에서 시작하며 stack도 비어있다.

 

i = 0.

maxLeft = 3이되며 stack이 아직 비어있으니 while문이 실행되지 않고 for문도 실행되지 않는다.

이후 stack에 3이 들어가게 된다.

 

i = 1.

maxLeft는 3이며 min은 1이다. stack.peek()이 1보다 크니 while문이 실행되지 않고, for문도 실행되지 않는다.

stack = {3, 1}

 

i = 2.

maxLeft는 3이며 min은 2이다. stack.peek()이 2보다 작으니 while문이 실행된다.

while (!stack.isEmpty() && stack.peek() < min) {
    sum += min - stack.pop();
    count++;
}

 

stack.pop()이 일어나 sum에 더해진다. sum = 1, stack = {3}, count = 1이 된다. 

이후 stack.peek()이 3이되어 min보다 커진다. while문은 종료된다.
이후 count만큼 다음 for문이 진행된다.

for (int j = 0; j < count; j++) {
    stack.add(num);
}
stack.add(num);

 

num은 지금 위치의 고도니까 2가 stack에 추가 된다.
stack = {3, 2}이며, for문이 종료된 후 2가 한번 더 추가된다.
stack = {3, 2, 2}

 

 

i = 3.

채워진 곳에는 물 표시를 해 놓겠다.
현 위치의 고도가 3이고 maxLeft = 3이니 min = 3이다.

while문에 따라 sum += 1이 두번 진행된다. sum = 3, stack = {3}, count = 2가된다.

이후 count만큼 stack에 3이 채워 넣어지고 마지막으로 현 위치의 고도까지 add되니

stack = {3, 3, 3, 3} 이 된다.

 

i = 4.

maxLeft = 4가 되지만, min 값이 3이므로 stack.peek() 값이 min보다 작지 않다.

고로 while문과 for문이 진행되지 않고 stack만 늘어난다.

sum = 3, stack = {3, 3, 3, 3, 4}

 

i = 5, i = 6.

maxLeft는 그대로 4이고 stack.peek() 값이 min보다 작지 않다.

고로 stack만 갱신된다.

stack = {3, 3, 3, 3, 4, 1, 1}

 

i = 7.

maxLeft = 4이고 min값은 2가된다.
stack.peek() 값이 min보다 작은동안, 즉 두번 while문이 진행된다.

sum += 1이 두번 일어나 sum 값이 0이되고, stack = {3, 3, 3, 3, 4} 이다.

for count 문이 진행되며 stack = {3, 3, 3, 3, 4, 2, 2, 2}가 되며 과정이 끝이 난다.

 

종료.

sum = 5가 되고 5가 출력된다.

 

설명과정은 길었지만, 어려운 문제는 아니었다. 골드 저티어와 실버 고티어는 비슷한 것같다.