백준 알고리즘 파이썬(Python) 14719번 빗물

---

 

📌  투 포인터를 활용한 풀이

이 문제는 투 포인터를 생각해서 풀 수 있다.

우선 투포인터 방식답게 양쪽에 left와 right로 포인터를 정해준다.

이때 이 두 포인터는 index가 되어야 하므로

• left는 0
• right는 가로길이 -1 즉 블록 리스트의 길이 -1

 

여기서 핵심은 양쪽 포인터가 전체 중 가장 높은 블록을 향해 나아가야 한다는 점이다.

오른쪽이 더 크다면 left +=  1 을 해줘서 왼쪽 포인터를 오른쪽으로

왼쪽이 더 크다면 right -=  1을 해줘서 오른쪽 포인터를  왼쪽으로

 

 

이를 공식으로 나타내면 다음과 같다.

if left_max <= right_max:
    result += left_max - height[left]
    left += 1
else:
    result += right_max - height[right]
    right -= 1

 

여기서 left_max, right_max는 가장 높은 블록(기준)을 중심으로 왼쪽 오른쪽에서 지금까지 가장 높은 블록의 높이이다.

 

지금 까지 설명한 것을 그림으로 나타내면 다음과 같다.

 

이 그림에서는 left_max는 3으로 유지가 되고 right_max는 2로 유지된다.

따라서 left_max - height[left] 는 result에 2 + 1 이렇게 쌓이게 되고 

right_max - height[right]는 result에 1 + 1 이렇게 쌓이다가 최대인 블록 즉 인덱스가 5인 지점에서 while문이 끝나게 되면서 최종 result는 5가 된다.

 

 

 

 

 

📖  전체코드

n, m = map(int, input().split())
height = list(map(int,input().split()))

left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
result = 0

# height가 빈 리스트라면 0을 return
if not height:
    print(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)