[알고리즘]빗물트래핑

2021.10.21 02:30

안녕하세요

프로그래밍을 배우는 빛나는 샤트입니다.

 

[Python Algorithm Study]

*아래 내용은 파이썬 알고리즘 인터뷰 라는 서적을 공부하면 정리한 내용입니다.

빗물트래핑

• 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.
• 입력(height): [0,1,0,2,1,0,1,3,2,1,2,1]
• 출력: 6
• leetcode trapping-rain-water

Trapping Rain Water - LeetCode

 

# 입력
height = [0,1,0,2,1,0,1,3,2,1,2,1]

 

기둥사이에 물이 얼마나 찰 수 있는지 부피를 구하라. 정답: 6

풀이1 투 포인터를 최대로 이동

• 좌우 포인터를 활용하는 방법
• 가장 높은 막대를 활용 -> 좌우 포인터를 비교하며 가장 높은 막대로 포인터를 이동하면서 고인 물의 부피를 계속 더해간다.
• 최대 지점에서 만나게 되며 O(n)에 풀이가 가능
• left_max(좌측의 가장 높은 기둥 높이) 또는 right_max는 반복문이 작동해도 고정되게 하고 새로운 기둥의 높이값과의 차이를 계속 더해주는 방식

 

def trap_TwoPointer(height):
    if not height: return 0

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

    while left < right:
        left_max, right_max = max(height[left], left_max), max(height[right], right_max)

        # 더 높은 쪽을 향해 투 포인터 이동
        if left_max <= right_max:
            volume+=left_max - height[left]
            left+=1
        else:
            volume+=right_max - height[right]
            right-=1
    return volume

print(trap_TwoPointer(height)) # 6

 

풀이2 스택 쌓기

• for문을 이용해 좌측부터 쭉 진행하는데 현재 높이가 이전 높이보다 높다면(변곡점 발견) 물의 부피(가로*세로)를 volume라는 변수에 계속 더해준다.
• stack을 다 비우기 전까지 while을 이용해 물의 부피를 구해준다.
• stack을 이용해 pop()을 활용 -> stack.pop()은 변곡점이 있는 기둥의 높이보다 작은 높이를 의미
• 물의 세로값: 변곡점의 높이(현재값)와 현재값보다 작거나 같은 위치(stack에서 pop 후의 맨 끝 인덱스값)의 높이 중 작은 값을 구하고 -> 더 낮은 쪽의 높이만큼 물이 고이기 때문. 그리고 그 값에 pop()을 한 인덱스를 이용한 높이 값을 빼주면 된다. -> pop()위치의 기둥 높이만큼은 물이 없으므로.
• 물의 가로값: 현재 인덱스 - pop

 

def trap_stack(height):
    stack = []
    volume = 0

    for i in range(len(height)):
        # 변곡점을 만나는 경우 = 이전 높이보다 현재 높이가 더 높을때
        while stack and height[i] > height[stack[-1]]:
            # 스택에서 꺼낸다.
            top = stack.pop()

            # stack의 길이가 0이면 while 정지
            if not len(stack):
                break

            # 이전과의 차이만큼 물 높이 처리

            # 변곡점 위치의 높이보다 작거나 같은 높이를 가지는 인덱스 값
            idx = stack[-1]

            # 물이 차지하는 가로 길이
            distance = i - top

            # 물이 차지하는 세로 길이
            waters = min(height[i], height[idx]) - height[top]
            volume+= distance*waters
        stack.append(i)

    return volume

print(trap_stack(height)) # 6

 

---

+α...numpy array를 이용한 image display

"""
우리가 흔히 색은 0~255로 표현할 수 있는데 아래처럼 display를 해보면 노란색, 보라색, 푸른색 등으로 표현된다.
이는 matplotlib.pyplot의 기본 color map이 viridis이기 때문.
이는 우리가 입력한 값의 최소값~최대값을 0과 1사이의 값으로 normalization해서 표현한다.

그렇다면 아래 코드의 컨셉에 맞게 [최대값, 중간값, 최소값], [최소값, 중간값, 최대값], [중간값, 최소값, 최대값] 처럼 표현하면 시각화 결과가 똑같을까?
"""

import numpy as np
import matplotlib.pyplot as plt

# numpy array -> img display
test_arr1 = [255,125,0]
test_arr2 = [0,125,255]
test_arr3 = [125,0,255]

test_arr = np.array([test_arr1,test_arr2,test_arr3])
plt.imshow(test_arr)

matplotlib.pyplot로 표현(색깔이 이상하다)

아래 코드의 array를 확인하면 위의 array와는 값은 다르지만 컨셉(최대값, 중간값, 최소값)을 이용해 동일하게 생성했다.

display 결과도 동일하다.

# 위의 array의 값은 다르지만 display는 똑같다.
test_arr4 = [10,5,0]
test_arr5 = [0,5,10]
test_arr6 = [5,0,10]

test_arr_new = np.array([test_arr4,test_arr5,test_arr6])
plt.imshow(test_arr_new)

위의 시각화 결과와 동일하다

흑백으로 표현하기 위해서는 cmap='gray'를 지정해줘야 한다.

# 흑백으로 표현
# 흑백 표현을 하기 위해서는 cmap='gray'를 입력해야 한다.
plt.imshow(test_arr, cmap='gray')

흑백으로 표현

 

추가로 RGB도 표현해봤다.

# RGB로 표현
r = [255,0,0]
g = [0,255,0]
b = [0,0,255]

rgb = np.array([[r,r,r],
             [g,g,g],
              [b,b,b]])

plt.imshow(rgb)

영롱한 RGB

 

그렇다면 문제에서 주어진 list를 가지고 책에 나와있는 모양처럼 numpy array를 이용해 시각화를 하고 싶어졌다.

방법은 ones 메소드를 이용해 모든 값이 1인 array를 만든후 (번거롭지만) 2중 for loop을 이용해 행,열을 하나씩 비교하면서 해당하는 칸에는 값을 0으로 바꿔서 검은색으로 표현했다.

# 한 행씩 생성
height = [0,1,0,2,1,0,1,3,2,1,2,1]
max_val = max(height)

img_arr = np.ones((max_val, len(height)))

compare_list = height

compare_max_val = max_val
for row in range(max_val):
    for col in range(len(compare_list)):
        if compare_max_val - compare_list[col] == 0:
            img_arr[row,col] = 0
            compare_list[col]-=1
    compare_max_val-=1

plt.imshow(img_arr, cmap='gray')

특정 픽셀만 검은색으로 변경

*참고글

[파이썬 matplotlib] 이미지맵(imshow)의 원리

 

여러분의 빛나는 코딩을 응원하며

샤트