파이썬 백준 알고리즘: 빗물 트래핑 14719

안녕하세요! 저는 당신을 위해 파이썬 알고리즘 풀이 포스트를 작성할 개발자입니다. 이번 포스트에서는 "빗물 트래핑" 문제를 다루어보려고 합니다. 빗물 트래핑은 주어진 지형에서 비가 내렸을 때 얼마나 많은 빗물이 쌓일 수 있는지를 계산하는 문제입니다.

문제 내용

주어진 지형은 가로로 w만큼의 너비를 가지고 있고, 각 지점마다 높이가 주어집니다. 빗물은 이 지형에 쌓이게 되는데, 빗물이 쌓이는 부분은 양 옆으로 높은 지점이 있을 때 그 사이의 낮은 부분입니다. 이 문제에서는 총 얼마나 많은 빗물이 쌓이는지를 계산해야 합니다.

문제 이해하기

먼저, 입력으로 주어지는 값은 가로 너비(w)와 각 지점의 높이를 나타내는 리스트(blocks)입니다. 이 문제에서는 가장 먼저 높이가 가장 큰 지점을 찾아야 합니다. 그러기 위해 move() 함수를 사용합니다. 이 함수는 시작 인덱스(idx), 가로 너비(w), 그리고 높이 정보를 담은 리스트(blocks)를 입력으로 받습니다. move() 함수는 시작 인덱스 다음부터 높이를 비교하면서 더 높은 지점이 나타나면 해당 인덱스를 반환합니다. 만약, 현재 인덱스의 높이보다 크거나 같은 지점을 찾으면 빗물이 쌓이는 영역이므로 해당 인덱스를 반환하고 종료합니다. 이때, 높이가 가장 큰 지점을 찾아야 하므로 현재까지의 최대 높이를 저장하고 비교합니다.

높이가 가장 큰 지점을 찾았다면, 이제 빗물이 얼마나 쌓이는지 계산할 차례입니다. rain() 함수는 시작 인덱스(idx), 가장 높은 지점의 인덱스(max_idx), 그리고 높이 정보를 담은 리스트(blocks)를 입력으로 받습니다. 이 함수는 시작 인덱스와 가장 높은 지점 사이의 낮은 부분에 빗물이 쌓이게 됩니다. 따라서 시작 인덱스와 가장 높은 지점 사이의 각 인덱스에 대해 최대 높이에서 해당 지점의 높이를 뺀 값을 누적하여 총 빗물의 양을 계산합니다.

마지막으로, main() 함수에서는 입력으로 주어지는 가로 너비와 높이 정보를 받아옵니다. 그리고 반복문을 사용하여 빗물이 쌓이는 부분을 계산하고 누적하여 총 빗물의 양을 구합니다. 계산이 끝나면 총 빗물의 양을 출력합니다.

풀이 코드

pythonCopy code
def move(idx, w, blocks):
    max_idx, max_height = idx, 0
    for i in range(idx + 1, w):
        if blocks[i] >= blocks[idx]:
            return i

        if blocks[i] >= max_height:
            max_height = blocks[i]
            max_idx = i
    return max_idx

def rain(idx, max_idx, blocks):
    total_rain = 0
    max_height = min(blocks[idx], blocks[max_idx])
    for i in range(idx + 1, max_idx):
        total_rain += max_height - blocks[i]
    return total_rain

def main():
    h, w = map(int, input().split())
    blocks = list(map(int, input().split()))

    idx, answer = 0, 0
    while idx < w - 1:
        max_idx = move(idx, w, blocks)
        answer += rain(idx, max_idx, blocks)
        idx = max_idx
    print(answer)

if __name__ == '__main__':
    main()

풀이 방법

1. move() 함수를 사용하여 높이가 가장 큰 지점을 찾습니다.
2. rain() 함수를 사용하여 시작 인덱스와 가장 높은 지점 사이의 낮은 부분에 빗물이 쌓이는 양을 계산합니다.
3. main() 함수에서 반복문을 통해 빗물이 쌓이는 부분을 계산하고 누적하여 총 빗물의 양을 구합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(N)입니다. move() 함수와 rain() 함수에서 반복문을 사용하며, 각 반복문은 최대 가로 너비(w)만큼 반복합니다. 따라서 전체적인 시간 복잡도는 O(N)입니다.