문제 링크
문제
문제가 간단하고 재미있었다.
4 4
3 0 1 4위와같이 2차원세계의 높이, 넓이와 각 기둥의 높이값이 주어진다.
빗물이 고일 수 있는 최대치를 구하는 문제이다.
풀이
처음에는 뭔가 Stack 자료구조에 적합한 입력이라고 생각해서 고민을 해봤지만 쉽지 않았다. Stack은 peek값과 현재 확인하는 값 두가지를 비교해서 뭔가 결정해낼 수 있어야 한다. 하지만 이 문제에서는 더 넓은 범위를 확인해야하기 때문에 복잡해질 것 같았다.
투포인터를 활용해 문제를 해결했다.
빗물이 고이는 경우는 양쪽에 자신보다 큰 기둥이 있는 경우이다.
-
현재
i번째까지 기둥의 최대값의 인덱스를left에 저장한다. -
block[left]보다 크거나 같은 기둥이 나온 경우 그 사이에는 빗물이 고인다. 따라서 그 사이에 고이는 빗물의 양을 계산해서answer을 업데이트 한다.
이 풀이의 문제점은 처음 left인덱스가 갱신이 되지 않을 때이다. 또 마지막 기둥이 큰 기둥이라는 보장이 없다. 이에 대한 처리를 추가로 해줘야 한다.
ex)
4 8
4 1 2 3 3 1 1 1따라서 1, 2번 과정을 진행해 준 후 마지막에 추가로 남은 것들에 대한 계산을 진행한다.
더 크거나 같은 기둥이 나온 경우는 처리해줬으므로 1,2,번을 진행한 후 left와 right 사이의 block에서 크기가 증가하는 경우는 없다. 즉 left 방향에 가장 큰 기둥이 존재한다.
따라서 right에서 시작해서 peek값을 업데이트 하며 answer을 추가로 업데이트 해준다.
import java.io.*;
import java.util.*;
public class Main{
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int H, W, answer = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
int[] block = new int[W];
st = new StringTokenizer(br.readLine());
for(int i=0; i<W; i++){
block[i] = Integer.parseInt(st.nextToken());
}
//1,2,번 과정
int left = 0, right = 0;
while(right<W){
if(block[left] <= block[right]) {
for (int i = left + 1; i < right; i++) {
answer += block[left] - block[i];
}
left = right;
}
right++;
}
//추가 작업
int peek = block[right-1];
for(int i= right-1; i>left; i--){
peek = Math.max(peek, block[i]);
answer+= peek-block[i];
}
System.out.println(answer);
br.close();
}
}더 좋은 풀이
다른 사람 풀이를 확인하며 더 이해하기 쉽고 간단한 풀이를 보았다.
논리는 다음과 같다.
어떤 위치 i에서 고이는 빗물의 양은 i기준 좌측 최대값 기둥 leftMax[i]와 우측 최대값 rightMax[i] 중 작은 값과 block[i]를 빼준 값이다.
leftMax와 rightMax를 모두 초기화해둔 후 위의 작업을 진행하며 빗물의 양을 계산할 수 있다.
