[파이썬, Java] 14719. 빗물

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

예제 입력 1 

4 4

3 0 1 4

예제 출력 1 

5

예제 입력 2 

4 8

3 1 2 3 4 1 1 2

예제 출력 2 

5

예제 입력 3 

3 5

0 0 0 2 0

예제 출력 3 

0

힌트

힌트 1:

힌트 2:

힌트 3:

 

 

 

🐩 나의 풀이

import sys
input=sys.stdin.readline

H, W=map(int, input().split())      # 세로, 가로
heights=list(map(int, input().split()))
left=heights[0]
right=heights[-1]
max_height=heights.index(max(heights))
left_sum=0
right_sum=0
ans=0

for l in range(1, max_height+1) :
    if left > heights[l] :
        left_sum+=left-heights[l]
    elif left <= heights[l] :
        ans+=left_sum
        left_sum=0
        left=heights[l]

for r in range(W-2, max_height-1, -1) :
    if right > heights[r] :
        right_sum+=right-heights[r]
    elif right <= heights[r] :
        ans+=right_sum
        right_sum=0
        right=heights[r]
print(ans)

왼쪽에서 가장 높은 블럭 위치 max_height까지, 오른쪽에서 max_height까지 for문을 돌렸다.

left와 right는 맨 왼쪽과 맨 오른쪽으로 시작점을 의미한다.

더 높은 기둥을 만나면 left 또는 right는 갱신된다.

 

 

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));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int H=Integer.parseInt(st.nextToken());        // 세로
        int W=Integer.parseInt(st.nextToken());         // 가로
        int[] arr=new int[W];
        int[] heights=new int[W];
        int tmp=-1;
        int ans=0;
        st=new StringTokenizer(br.readLine());

        for(int i=0; i<W; i++){
            arr[i]=Integer.parseInt(st.nextToken());
    }
        for(int i=W-1; i>=0; i--){
            if(tmp < arr[i]){
                tmp=arr[i];
            }
            heights[i]=tmp;
        }

        int num=arr[0];
        int a=0;
        for(int i=1; i<W; i++){
            a=Math.min(num, heights[i])-arr[i];
            if(a > 0){
                ans+=a;
            }else{
                num=arr[i];
            }
        }

        System.out.println(ans);
}
}

다른 사람의 파이썬 풀이를 자바로 구현해봤다.

heights 배열에 오른쪽에서 봤을 때 arr[i]블럭 높이보다 더 높은 블럭의 높이를 넣는다.

num은 이전 블럭 중 가장 높은 블럭이다.

num과 i의 오른쪽에 있는 블럭 중 높은 블럭 heights[i] 둘중 최소값-arr[i]가 양수여야한다.

빗물이 고이려면 양쪽 블럭이 현재 블럭 i보다 높아야한다는 뜻이다.

 

 

# 실패
import sys
input=sys.stdin.readline

H, W=map(int, input().split())      # 세로, 가로
heights=list(map(int, input().split()))
left=heights[0]
right=heights[-1]
max_height=heights.index(max(heights))
left_sum=0
right_sum=0
ans=0

for l in range(1, max_height+1) :
    if left > heights[l] :
        left_sum+=left-heights[l]
    elif left <= heights[l] :
        ans+=left_sum
        left_sum=0

for r in range(W-2, max_height-1, -1) :
    if right > heights[r] :
        right_sum+=right-heights[r]
    elif right <= heights[r] :
        ans+=right_sum
        right_sum=0
print(ans)

이 풀이를 고쳐서 통과한 코드가 맨위에 있다.

반례가 뭐가 있을까??

문제의 테케는 통과하는데..

왼쪽, 오른쪽 각 방향에서 가장 높은 블럭까지 for문을 돌린다.

시작점보다 더 높은 블럭을 만나면 모은 빗물(left_sum 또는 right_sum)을 ans에 더했다.

 

 

🍟 다른 사람 풀이

# https://namhandong.tistory.com/139
import sys
input=sys.stdin.readline

maxH=1
maxL=0

H, W=map(int, input().strip().split())

pillar=list(map(int, input().strip().split()))
for i in range(len(pillar)) :
    if maxH < pillar[i] :
        maxH=pillar[i]      # 가장 높은 기둥
        maxIndex=i          # 가장 높은 기둥 인덱스

total=0
temp=0
for i in range(maxIndex+1) :	# 왼쪽 방향
    if pillar[i] > temp :
        temp=pillar[i]
    total+=temp
temp=0
for i in range(W-1, maxIndex, -1) :		# 오른쪽 방향
    if pillar[i] > temp :
        temp=pillar[i]
    total+=temp
print(total-sum(pillar))

temp는 i-1까지 가장 높은 기둥의 높이다.

더 높은 기둥 pillar[i]를 발견하면 temp를 갱신한다.

왼쪽에서 가장 높은 기둥까지 최대값, 오른쪽에서 가장 높은 기둥전까지 최대값의 합이 total이다.

 

 

H, W=map(int, input().split())		# 세로, 가로
A=list(map(int, input().split()))
M=[]
m=-1
for i in range(len(A)-1, -1, -1) :	# 왼쪽
    if m < A[i] : m=A[i]
    M=[m]+M

R=0
m=A[0]
for i in range(1, len(A)-1) :	# 오른쪽
    t=min(m, M[i])-A[i]
    if t > 0 : R+=t
    if m < A[i] : m=A[i]
print(R)

마지막 블럭에서 처음 블럭까지 왼쪽 방향으로 반복문을 돌린다.

더 높은 블럭 A[i]를 발견하면 m을 갱신한다.

지문의 테케는 M=[4, 4, 4, 4, 4, 2, 2, 2]이다.

M[i]는 i의 오른쪽에 있는 가장 높은 기둥의 높이다.

A[0]=3보다 높은 기둥은 A[4]=4고, A[6]보다 높은 기둥은 A[7]=2다.

1부터 오른쪽 방향으로 for문을 돌린다.

왼쪽에서 봤을 때와 오른쪽에서 봤을 때 중 더 작은 블럭을 고른다.

min(m, M[i])에서 현재 블럭 높이 A[i]를 뺀 값이 양수면 빗물이 고인다.

음수면 A[i]가 더 크니까 m을 갱신한다.

 

 

import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args) throws Exception {
        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());

        int[] map=new int[W];
        int[] left=new int[W];
        int[] right=new int[W];
        int[] newMap=new int[W];

        st=new StringTokenizer(br.readLine());
        for(int i=0; i<W; i++){
            map[i]=Integer.parseInt(st.nextToken());
        }

        // 왼쪽에서부터 시작한 배열 갱신
        int curHeight=0;
        for(int i=0; i<W; i++){
            if(curHeight < map[i]){
                curHeight=map[i];
            }
            left[i]=curHeight;
        }

        // 오른쪽 값 계산
        curHeight=0;
        for(int i=W-1; i>=0; i--){
            if(curHeight < map[i]){
                curHeight=map[i];
            }
            right[i]=curHeight;
        }

        for(int i=0; i<W; i++){
            newMap[i]=Math.min(left[i], right[i]);
        }

        int answer=0;
        for(int i=0; i<W; i++){
            answer+=(newMap[i]-map[i]);
        }
        System.out.println(answer);
    }
}

왼쪽, 오른쪽에서 봤을 때를 구한다.

newMap[i]는 왼쪽에서 봤을 때와 오른쪽에서 봤을 때중에서 더 작은 값이다.

 

 

import java.io.*;

class Main{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] ss=br.readLine().split(" ");
        int N=Integer.parseInt(ss[1]);

        int[] bricks=new int[N];
        ss=br.readLine().split(" ");

        int answer=0;
        int max=0;
        int sum=0;
        for(int i=0; i<N; i++){
            bricks[i]=Integer.parseInt(ss[i]);
            if(bricks[i] > 0 && max == 0){
                max=bricks[i];
            }else if(max < bricks[i]){
                answer+=sum;
                max=bricks[i];
                sum=0;
            }else{
                sum+=max-bricks[i];
            }
        }
        max=0;
        sum=0;
        for(int i=N-1; i >= 0; i--){
            if(bricks[i] > 0 && max == 0){
                max=bricks[i];
            }else if(max <= bricks[i]){
                answer+=sum;
                max=bricks[i];
                sum=0;
            }else{
                sum+=max-bricks[i];
            }
        }
        System.out.println(answer);
    }
}

내 파이썬 풀이랑 같은 로직이다.

나처럼 가장 높은 0~기둥, 마지막~기둥-1까지 반복하지 않고, 전체적으로 돌렸다.

높은 기둥을 만나면 max=bricks[i]로 갱신하고, 빗물의 총량 ans에 sum을 더한다.

sum은 일시적인 빗물 총량이다.

 

 

문제 출처 👉 백준