[구현] 14719번 - 빗물

[백준] 14719번 - 빗물

📝 나의 풀이 - Stack

Stack을 사용해 원하는 값에 도달할 때까지 기존 값들을 계속해서 쌓아두고,
원하는 값이 나타나면 그 순간까지 쌓아둔 값들을 모두 꺼내 처리할 수 있다.

벽의 높이가 [4, 1, 1, 3, 5]로 주어졌다고 가정해 보자.

1. 스택 초기화 및 변수 설정
limit 변수에 첫번째 벽을 기록해두고, 스택을 초기화 한다.

2. 벽의 높이를 순차적으로 확인
limit 벽의 높이가 스택에 저장된 마지막 벽의 높이보다
낮거나 같으면 스택에 인덱스를 푸시한다.

3. 높은 벽을 만났을 때 처리
limit 벽의 높이가 스택의 마지막 벽의 높이보다 높을 경우
스택에 저장된 이전 벽들과의 차이를 계산하여 물이 고일 수 있는 양을 계산한다.
계산 후, limit 갱신

4. 모든 숫자 입력 후 Stack이 비어있지 않은 경우

[4, 1, 1, 2] 의 경우를 예로 들 수 있다.
end와 tmp 사이에 고인 빗물의 양을 구한다.

int end = block.pop();

👩🏻‍💻 stack을 이용한 코드

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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		
		
		st = new StringTokenizer(br.readLine());
		Stack<Integer> block = new Stack<>();
		int answer = 0;
		int limit = Integer.parseInt(st.nextToken());
		
		while(st.hasMoreTokens()) {
			int tmp = Integer.parseInt(st.nextToken());
			
			if(tmp >= limit) {
				while(!block.isEmpty()) {
					answer += (limit - block.pop());
				}
				limit = tmp;

			}
			else {
				block.push(tmp);
			}
						
		}
		
		
		if(!block.isEmpty() && block.size() > 1) {
			int end = block.pop();
			
			while(!block.isEmpty()) {
				int tmp = block.pop();
				if(tmp < end) {
					answer += end - tmp;
				}
				else {
					end = tmp;
				}
			}
		}
		
		System.out.println(answer);
		
	}

}

📝 다른 풀이 - 구현

🔥 빗물이 고이는 조건

첫번째 열과 마지막 열은 물이 고일 수 없다.

1. 왼쪽으로 자신보다 높은 블럭이 존재
2. 오른쪽으로 자신보다 높은 블럭이 존재

이 두가지 조건에 만족할 때 빗물 고이는 양을 계산하면 된다.
왼쪽 가장 높은 블럭, 오른쪽 가장 높은 블럭 중 더 작은 높이 만큼 빗물이 고인다.

👩🏻‍💻 구현을 이용한 코드

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		
		
		st = new StringTokenizer(br.readLine());
		int[] block = new int[W];
		int answer = 0;
		
		for(int i = 0; i < W; i++) {
			block[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 1; i < W-1; i++) {
			int cur = block[i];
			int left = 0, right = 0;
			
			for(int j = i - 1; j >= 0; j--) {
				left = Math.max(left, block[j]);
			}
			
			for(int j = i + 1; j < W; j++) {
				right = Math.max(right, block[j]);
			}
			
			
			if(cur < left && cur < right) {
				answer += Math.min(left, right) - cur;
			}
		}
		
		System.out.println(answer);
		
	}

}

---

Reference

백준 14719 빗물 자바
[백준] 알고리즘 분류(구현,JAVA)14719번, 빗물