문제는 다음과 같다.
https://www.acmicpc.net/problem/14719
풀이는 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st1 = new StringTokenizer(br.readLine());
int H = Integer.parseInt(st1.nextToken());
int W = Integer.parseInt(st1.nextToken()); //W 1이면 답 0
StringTokenizer st2 = new StringTokenizer(br.readLine());
Stack<Integer> s = new Stack<>();
int start = Integer.parseInt(st2.nextToken());
int answer = 0;
while(st2.hasMoreTokens()) { //도중에 더 높은거 만나면, 싹다 비워내고 고인 물 세주는 로직 (1, 4번)
int tmp = Integer.parseInt(st2.nextToken());
if(tmp >= start) {
while(!s.isEmpty()) {
answer += start - s.pop();
}
start = tmp;
}
else {
s.add(tmp);
}
}
if(!s.isEmpty() && s.size() > 1) { //전부 끝나고 나서, 도중에 더 높은걸 안만났다고 생각해보자 (2번, 3번, 5번)
int end = s.pop();
while(true) {
if(s.isEmpty()) break;
int cur = s.pop();
if(cur > end) {
end = cur;
}
else {
answer += end - cur;
}
}
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
}
풀이 안의 주석에서, 1번부터 5번까지는 위의 그림을 의미하는것이다.
스택을 이용해서 풀었다.
뭔가 예전부터
내가 원하는 값을 만나면, 원하는 값 이외의 값을 만날때까지
기존의 값들을 와다다다 제외하면서 원하는 로직대로 처리해주는 내용.
이러한 내용은 보통 스택으로 풀었기에,
어.. 이친구도 스택인가..? 를 생각해서 풀어줬다.
지금부터 문제풀때 생각했던 내용을 설명하겠다.
기록된 높이의 벽보다
그 이상의 벽을 예로 들겠다. (위 그림의 1번 4번)
주어진 숫자들(벽의 높이들 전체)을 전부 입력받으며 계산했다.
예를 들어,
4 1 1 3 5 를 생각해보자.
기록된 높이의 벽 = 4
그다음 벽 1 < 4 (스택에 넣기)
그다음 벽 1 < 4 (스택에 넣기)
그다음 벽 3 < 4 (스택에 넣기)
그다음 벽 5 >= 4
기록된 높이보다 더 높은게 나왔으므로, 기존에 스택에 있던 친구들을 전부 꺼내서 빗물 고여주고, (4-1, 4-1, 4-3 더해주고)
기록된 높이를 갱신해준다.(start = tmp)
while(st2.hasMoreTokens()) { //도중에 더 높은거 만나면, 싹다 비워내고 고인 물 세주는 로직 (1, 4번)
int tmp = Integer.parseInt(st2.nextToken());
if(tmp >= start) {
while(!s.isEmpty()) {
answer += start - s.pop();
}
start = tmp;
}
else {
s.add(tmp);
}
}
그다음, 모든 숫자를 사용했는데,
기록된 높이 이상의 벽이 안나와서 스택이 텅 비지 않은채로 바로 위의 while문을 마쳤다면..?
(위의 2번, 3번, 5번 경우)
해당 경우가 아래의 로직이다.
바로 위에서 설명한 굵은 글씨의 로직을 이해했다면, 이 로직도 쉽게 이해가 갈 것이다.
if(!s.isEmpty() && s.size() > 1) { //전부 끝나고 나서, 도중에 더 높은걸 안만났다고 생각해보자 (2번, 3번, 5번)
int end = s.pop();
while(true) {
if(s.isEmpty()) break;
int cur = s.pop();
if(cur > end) {
end = cur;
}
else {
answer += end - cur;
}
}
}
풀이 하나 더!
구현으로 풀었다. 주석에 설명이 있어 이해할 수 있다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st1 = new StringTokenizer(br.readLine());
int h = Integer.parseInt(st1.nextToken());
int w = Integer.parseInt(st1.nextToken());
int[] blocks = new int[w];
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i = 0 ; i < w ; i++) {
blocks[i] = Integer.parseInt(st2.nextToken());
}
int answer = 0;
//빗물이 고일 수 있는 블럭 하나하나마다, 양 옆을 탐색하여 해당 블럭 하나에 고이는 빗물을 더해줄 예정임.
//3 0 1 4 에서 0은, 양옆의 3과 4에 가로막혀 빗물이 고이고, 3-0만큼의 빗물이 고인다. 이런식으로
for(int i = 1 ; i < w-1 ; i++) { //처음과 끝은 빗물이 고일 수 없으므로 제외
int curH = blocks[i];
int lm = 0; //어느 index 기준으로 왼쪽에서 높이최대 기록
int rm = 0;
for(int j = i-1 ; j >= 0 ; j--) {
lm = Math.max(lm, blocks[j]);
}
for(int j = i+1 ; j < w ; j++) {
rm = Math.max(rm, blocks[j]);
}
//lm과 rm이 둘다 지금 현재 높이보다 높다면 빗물 고이므로,
//둘 중 더 적은값(적은값을 기준으로 빗물이 고이니까)과 현재 높이를 빼줌
if(lm > curH && rm > curH) answer += Math.min(rm, lm) - curH;
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
}