/ BOJ

BOJ_14719_빗물_JAVA

문제 : 입국심사

링크 : BOJ_14719_빗물

접근 방식

예전에 풀었던 창고다각형 문제와 유사한 문제였다.

양쪽이 벽으로 둘러쌓여있는 공간에 빗물을 채우고, 그 빗물의 넓이를 구해야 한다.

내가 생각한 풀이 방식은 다음과 같다.

  1. 가장 높은 기둥을 찾는다.

  2. 양쪽으로 탐색하며 각각 2번째로 높은 기둥을 찾는다.

  3. 찾은 기둥으로부터 가장 높은 기둥으로의 넓이를 구한다.

  4. 2번째의 기둥을 다시 기준삼아서 각각의 방향으로 또다시 더 작은 기둥을 찾는다.

  5. 위 로직을 기둥의 끝에 도달할 때까지 반복한다.

  6. 반복이 모두 종료된 후 전체 면적에서 기둥의 면적을 빼준다.

기둥의 면적은 값으로 주어지기 때문에, 전제 도형의 넓이를 구한 뒤에 기둥의 넓이를 빼는 방식으로 문제를 풀이했다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_14719_빗물 {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		// 정수형 배열 리스트 선언 및 생성
		List<int[]> list = new ArrayList<>();

		int N = Integer.parseInt(st.nextToken());

		int M = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(in.readLine(), " ");
		int check = 0;
		for (int i = 0; i < M; i++) {
			int temp = Integer.parseInt(st.nextToken());
			check += temp;
			if (temp != 0) {
				list.add(new int[] { i, temp });
			}
		}
		//오른쪽
		int X = 0;
		//왼쪽
		int Y = 0;
		//높이
		int H = 0;

		for (int i = 0; i < list.size(); i++) {
			// 높이가 최댓값인 수
			if (H <= list.get(i)[1]) {
				X = i;
				Y = i;
				H = list.get(i)[1];
			}
		}

		int ans = 0;

		ans += list.get(X)[1];
		// 오른쪽 탐색
		while (true) {
			int secondH = 0;

			int x = 0;

			if (X + 1 >= list.size()) {
				break;
			}

			for (int i = X + 1; i < list.size(); i++) {
				if (list.get(i)[1] > secondH) {
					secondH = list.get(i)[1];
					x = i;
				}
			}
			ans += (list.get(x)[0] - list.get(X)[0]) * list.get(x)[1];
			X = x;
		}

		// 왼쪽 탐색
		while (true) {
			int secondH = 0;
			int y = 0;

			if (Y - 1 < 0) {
				break;
			}
			for (int i = Y - 1; i >= 0; i--) {
				if (list.get(i)[1] > secondH) {
					secondH = list.get(i)[1];
					y = i;
				}
			}
			ans += (list.get(Y)[0] - list.get(y)[0]) * list.get(y)[1];
			Y = y;
		}
		System.out.println(ans - check);
	}
}