https://www.acmicpc.net/problem/14719
14719번: 빗물
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치
www.acmicpc.net
[정답 코드]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
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[] arr = new int[W];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < W; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int answer = 0;
for (int i = 1; i < W - 1; i++) { // 처음벽과 마지막벽에는 물이 고일수 없다
int current = arr[i]; // 현재 벽의 높이
int leftMax = current; // 왼쪽 벽
int rightMax = current; // 오른쪽 벽
for (int j = i - 1; j >= 0; j--) { // 왼쪽 벽 최대 높이 탐색
if (arr[j] > current) {
leftMax = Math.max(leftMax, arr[j]);
}
}
for (int j = i + 1; j < W; j++) { // 오른쪽 벽 최대 높이 탐색
if (arr[j] > current) {
rightMax = Math.max(rightMax, arr[j]);
}
}
if (Math.min(leftMax, rightMax) > current) { // 현재 벽보다 높은 벽이 양쪽에 있는 경우
answer += (Math.min(leftMax, rightMax) - arr[i]);
}
}
System.out.println(answer);
}
}
[설명]
처음에는 구현문제가 쉬운 문제인줄 알았는데 풀면 풀 수록 구현 문제도 어렵다는걸 깨달았다. 이 문제는 다른 블로그들을 대부분 참고했다.
문제 풀이방법은 for문을 돌며 현재 벽 기준으로 왼쪽 벽 중 가장 높은벽과 가장 높은 오른쪽 벽을 구한 후, 그 벽들이 현재 벽보다 높을 경우 빗물이 고이기 때문에 높은 벽에서 현재 벽을 빼주면 그 차이 만큼 빗물이 쌓인다.
이때 문제의 핵심은 두가지가 있다.
1. 가장 왼쪽벽과 가장 오른쪽 벽에는 빗물이 고일 수 없다.
그래서 for문을 돌릴때 i = 1부터 시작되고 끝은 W - 1까지 한다.
2. 현재 벽보다 높은 양쪽 벽중에 더 낮은 벽 기준으로 빗물이 고인다.
예를 들면 빨간 체크한 벽이 for문에서 현재 current 라고 했을 때, 왼쪽벽 중 가장 높은벽은 4 이고 오른쪽벽 중 가장 높은 벽은 2이다. 이때 그림으로 보면 알 수 있듯이 왼쪽벽을 기준으로 계산하는게 아닌 오른쪽 벽을 기준으로 계산해야 한다.
'코딩테스트' 카테고리의 다른 글
| 백준 5972번: 택배 배송[JAVA] (0) | 2024.03.07 |
|---|---|
| 백준 5972번: 택배 배송[JAVA] (0) | 2024.03.05 |
| 백준 14940번: 쉬운 최단거리[JAVA] (1) | 2024.02.29 |
| 백준 1072번: 게임[JAVA] (0) | 2024.02.15 |
| 백준 1920번: 수 찾기[JAVA] (0) | 2024.02.14 |
