백준 - 14719 빗물 [구현]

 

14719번: 빗물

 

1. 문제 요약

블록들의 높이가 주어지고 블록들 사이에 고일 수 있는 빗물의 양을 구하는 문제입니다.

 

2. 파이썬

2 - 1. 접근 방법

백준 - 2304 창고 다각형 [구현]

이전에 풀었던 문제와 거의 유사하여 해당 방식을 다시 사용했습니다.

가장 높은 블록을 기준으로 세 부분으로 나누어 진행했습니다.

 

2 - 2. 코드

def solution(w: int, blocks: list):
    answer = 0
    highest = max(blocks)

    # 정방향
    now_highest = 0
    stop_index1 = 0
    for i in range(w):
        if blocks[i] >= highest:
            stop_index1 = i
            break
        elif blocks[i] < now_highest:
            answer += now_highest - blocks[i]
        else: # blocks[i] > now_highest:
            now_highest = blocks[i]

    # 역방향
    now_highest = 0
    stop_index2 = 0
    for i in range(w - 1, -1, -1):
        if blocks[i] >= highest:
            stop_index2 = i
            break
        elif blocks[i] < now_highest:
            answer += now_highest - blocks[i]
        else:
            now_highest = blocks[i]

    # 중간 부분 계산
    for i in range(stop_index1 + 1, stop_index2):
        answer += highest - blocks[i]

    print(answer)

h, w = map(int, input().split())
blocks = list(map(int, input().split()))
solution(w, blocks)

 

3. 자바

3 - 1. 접근 방법

현재 위치에 물이 고일 수 있는 양에 집중하는 방법

즉, 현재 인덱스의 양 옆으로 자신보다 높은 블록이 존재하는지 체크하여 고일 수 있는 양을 계산한다.

 

3 - 2. 코드

// 메인 로직
static int solution(int[] blocks) {
    int answer = 0;

    for (int i = 1; i < blocks.length - 1; i++) {
        int leftHighest = getMax(blocks, 0, i);
        int rightHighest = getMax(blocks, i + 1, blocks.length);

        int compare = Math.min(leftHighest, rightHighest);

        if (compare > blocks[i]) {
            answer += compare - blocks[i];
        }
    }

    return answer;
}

// 편의 메서드 다양한 방식으로 대체가능
private static int getMax(int[] arr, int start, int end) {
    int max = Integer.MIN_VALUE;
    for (int i = start; i < end; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

 

3 - 3. 전체 코드

https://github.com/Ksiyeong/Algorithm/blob/main/%EB%B0%B1%EC%A4%80/Gold/14719.%E2%80%85%EB%B9%97%EB%AC%BC/%EB%B9%97%EB%AC%BC.java