백준 14719 - 빗물

문제

https://www.acmicpc.net/problem/14719

풀이

문제 조건을 통해 정의한 ‘고인물’의 개념은 다음과 같다.

임의의 두 블록 사이 블록들이 두 블록보다 전부 작을 때 물이 고일 수 있다. 이 때 고이는 물의 양은 두 블록중 크기가 더 작은 블록과의 높이 차이를 기준으로 계산된다.

위 조건에 따라 입력으로 들어오는 블록의 높이들을 스택에 저장하며 이전까지 최고로 높았던 블록보다 더 높거나 같은 블록이 입력될 경우, 새 블록과 이전 최고 높이 블록 사이 블록들의 높이들을 통해 고인물의 양을 계산하여 누적하는 식으로 로직을 구성하였다.

한편, 위 예시같은 경우 최고 높이가 4로 갱신된 이후 해당 높이 블록보다 높거나 같은 블록이 들어오지 않고 입력이 끝나게 된다. 이럴 경우 별도의 처리를 통해 고인물의 양을 계산해주어야 했는데, 단순히 앞서 짠 로직을 역으로 적용하였다. 스택을 하나 더 형성하여 기존 스택에 저장했던 값을 역으로 탐색하며 동일한 연산을 그대로 적용해주면 된다.

로직의 시간복잡도는 사실상 선형으로 스택을 이용해 입력을 처리하므로 $O(N)$으로 생각할 수 있고 이는 $N=W=500$인 최악의 경우에도 무난히 제한 조건 1초를 통과한다.

코드

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		br.readLine(); // H, W 처리

		StringTokenizer st = new StringTokenizer(br.readLine());
		Stack<Integer> stack = new Stack<>();
		int maxH = parseInt(st.nextToken());
		stack.push(maxH);
		int sum = 0;
		while (st.hasMoreTokens()) {
			int h = parseInt(st.nextToken());

			if (h >= maxH) {
				while (!stack.isEmpty()
					&& stack.peek() <= maxH) {
					sum += maxH - stack.pop();
				}
				maxH = h;
				stack.push(h);
				continue;
			}

			stack.push(h);
		}

		if (stack.isEmpty()) {
			System.out.println(sum);
			return;
		}

		Stack<Integer> stack2 = new Stack<>();
		maxH = stack.pop();
		stack2.push(maxH);

		while (!stack.isEmpty()) {
			int h = stack.pop();

			if (h >= maxH) {
				while (!stack2.isEmpty()
					&& stack2.peek() <= maxH) {
					sum += maxH - stack2.pop();
				}
				maxH = h;
				stack2.push(h);
				continue;
			}

			stack2.push(h);
		}

		System.out.println(sum);
	}
}

결과