[BOJ/백준] 14719. 빗물 (Python)

🔎 문제

🔗 백준 14719번 빗물

💡 풀이

일단 기본적인 생각은 ‘오목한 곳에 빗물이 고임’ 이다. 낮은곳 옆에 어디든 그것보다 높은 곳만 있으면 빗물이 고인다.

브루트 포스(brute force), 투포인터(two pointer)로 풀 수 있는데, 투포인터가 더 효율적이다.

📍 투포인터

left, right 두 포인터가 있다. left는 왼쪽, right는 오른쪽에서 시작한다. 인덱스는 left가 0, right가 W-1이다. left가 right보다 클 때까지 (만날때까지) while문을 돈다.

시작은 max_left = drops[left] , max_right = drops[right] 두개의 값을 비교한다. 그중 더 작은쪽의 빗물을 구하고 작은쪽의 포인터를 이동시킨다.

이후 매번 max_left와 max_right를 위치가 바뀐 포인터를 가지고 갱신한다. 그리고 위 과정을 반복한다. 아마 그려보면 이해가 될 것이다.

📍 브루트포스

각 열마다 빗물을 떨어뜨리고 그곳에 빗물이 담기는지, 안담기는지 판단한다.

그냥 해당 열의 왼쪽, 오른쪽에 그 열의 높이보다 크거나 같은것만 존재하면 된다. 매번 양쪽을 다 검사한다.
해당 열의 양옆의 최댓값을 각각 찾고, 그중 작은값으로 빗물을 계산한다.

맨 왼쪽과 맨 오른쪽은 빗물을 담아도 흐르므로 검사하지 않는다.

나는 좀 바보처럼 풀었는데, 좀 더 파이썬스럽게 풀 수도 있다. 파이썬 스럽게 푼 코드도 맨 아래에 첨부한다.

📃 소스코드

투포인터

H, W = tuple(map(int, input().split()))
drops = list(map(int, input().split()))

left, right = 0, W - 1
max_left = drops[left]
max_right = drops[right]

result = 0

while left < right:
    max_left = max(max_left, drops[left])
    max_right = max(max_right, drops[right])
    
    if max_left >= max_right:
        result += max_right - drops[right]
        right -= 1
    if max_left < max_right:
        result += max_left - drops[left]
        left += 1
        
print(result)

브루트포스(c,자바처럼)

# 입력은 위 코드와 동일
result = 0

for i in range(1, W - 1):
    max_left, max_right = -1, -1
    for j in range(i):
        if drops[j] >= drops[i]:
            max_left = max(max_left, drops[j])
    for k in range(i + 1, W):
        if drops[k] >= drops[i]:
            max_right = max(max_right, drops[k])
    if max_left != -1 and max_right != -1:
        MIN = min(max_left, max_right)
        result += MIN - drops[i] # 빗물계산
        
print(result)

브루트포스(파이썬스럽게, pythonic하게)

# 입력은 위 코드와 동일
result = 0

for i in range(1, W - 1):
    max_left = max(drops[:i + 1])
    max_right = max(drops[i:])
    MIN = min(max_left, max_right)
    result += abs(drops[i] - MIN)
        
print(result)

투포인터가 가장 빠르고, for문 도는것 보다 파이썬의 슬라이스를 이용한 풀이가 더 빠르다

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️