[Java] 백준(골드-5) 14719번 - 빗물
문제 풀이
이번 문제는 요구사항대로 잘 구현하면 된다.
아이디어 도출
빗물이 고이기 위한 조건은 무엇일까?
- 현재 블록의 높이보다 높은 블록이 왼쪽에 있어야 한다.
- 현재 블록의 높이보다 높은 블록이 오른쪽에 있어야 한다.
- 첫 블록과, 마지막 블록에는 빗물이 고일 수 없다.
아이디어 자체는 단순하다. 이 조건을 문제 풀이를 위한 아이디어로 접목시켜 보자.
- 첫 블록과 마지막 블록을 제외한 블록들을 탐색한다.
- 기둥들을 탐색하며 현재 기둥을 기준으로 왼쪽으로 가장 높은 기둥과, 오른쪽으로 가장 높은 기둥을 구한다.
- 현재 기둥이 양 옆의 기둥의 높이보다 낮다면 왼쪽, 오른쪽 기둥 중 낮은 기둥 높이 값에서 현재 기둥 높이값을 빼준다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
StringTokenizer st = new StringTokenizer(br.readLine());
int H = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());
int[] heights = new int[W];
st = new StringTokenizer(br.readLine());
for(int i=0; i<W; i++) {
heights[i] = Integer.parseInt(st.nextToken());
}
int result = 0;
// 1. 현재 블록 높이보다 왼쪽 블록이 높아야 한다.
// 2. 현재 블록 높이보다 오른쪽 블록이 높아야 한다.
// 3. 첫 줄 블록과 마지막 줄의 블록에는 빗물이 고일 수 없다.
for(int i=1; i<W-1; i++) {
// 현재 기둥
int now = heights[i];
// 왼쪽, 오른쪽 기둥 높이를 담을 변수
int left = 0;
int right = 0;
// 왼쪽에서 가장 높은 기둥을 구한다.
for(int j=0; j<i; j++) {
left = Math.max(heights[j], left);
}
// 오른쪽에서 가장 높은 기둥을 구한다.
for(int j=i+1; j<W; j++) {
right = Math.max(heights[j], right);
}
/**
* 현재 블록이 왼쪽, 오른쪽 블록보다 낮다면,
* 둘 중 더 낮은 기둥의 높이값으로 현재 기둥 높이값을 빼준다.
*/
if(now < left && now < right) {
result += Math.min(left, right) - now;
}
}
bw.write(result+"\n");
}
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.