[Two Pointers] 백준 14719번 “빗물” Python 풀이

문제 링크

• https://www.acmicpc.net/problem/14719

풀이

• 투 포인터 알고리즘을 사용해 해결할 수 있으며,
• 세부 알고리즘은 아래 예제 코드를 읽으며 이해하시면 도움이 될 것 같습니다.

코드

import sys

n, m = map(int, sys.stdin.readline().split())
height = list(map(int, sys.stdin.readline().split()))

# 가장 왼쪽 블록과 오른쪽 블록의 인덱스 저장
left, right = 0, len(height) - 1
# 가장 왼쪽 블록의 개수와 가장 오른쪽 블록의 개수로 초기화
left_max, right_max = height[left], height[right]

# 고인 물의 개수
result = 0

# 두 포인터가 만날때 까지 while문 진행
while left < right:

    # 왼쪽 포인터를 옮기며, 왼쪽 블록 중 최대 블록 개수를 업데이트
    left_max = max(left_max, height[left])
    # 오른쪽 포인터를 옮기며, 오른쪽 블록 중 최대 블록 개수를 업데이트
    right_max = max(right_max, height[right])

    # 왼쪽 최대 블록 개수보다 오른쪽 최대 블록 개수가 크거나 같다면
    if left_max <= right_max:
        # 왼쪽 최대 블록 개수와 현재 블록 개수의 차이만큼 물 채우기
        result += left_max - height[left]
        # 왼쪽의 인덱스를 증가
        left += 1

    # 왼쪽 최대 블록 개수가 오른쪽 최대 블록 개수보다 크다면
    else:
        # 오른쪽 최대 블록 개수와 현재 블록 개수의 차이만큼 물 채우기
        result += right_max - height[right]
        # 오른쪽의 인덱스를 감소
        right -= 1

print(result)