문제를 풀었는데, 책과 달라요

[WonJongWoon]

그런데, 본질적으로 책과 같은데, 방식만 다른건지, 문제가 있는 코드인지도 여기 올리면 봐주시나요..?
( 리트코드에 잘 제출됩니다. )

빗물 트래핑 문제입니다.

다음 코드는 제가 작성한 코드입니다.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: 
            return 0 

        volume = 0 # 빗물의 양
        max_height_index = height.index(max(height)) # 가장 높은 블럭의 위치
        left_height = height[:max_height_index+1]  # 가장 높은 블럭 좌측 구간
        right_height = list(reversed(height[max_height_index:])) # 가장 높은 블럭 우측 구간 반전

        left, right = 0, 1
        while right < len(left_height): 
            if left_height[left] > left_height[right]: 
                volume += left_height[left] - left_height[right] 
                right += 1 
            else: 
                left, right = right, right + 1  


        left, right = 0, 1
        while right < len(right_height):
            if right_height[left] > right_height[right]: 
                volume += right_height[left] - right_height[right] 
                right += 1 
            else:
                left, right = right, right + 1 
            
        return volume 

[likejazz]

좋은 알고리즘이네요. 수고하셨습니다.
제가 볼때는 문제 없이 잘 동작하는거 같네요.

당연한 얘기지만 책에 있는 풀이는 하나의 예 일 뿐이고 다른 방법으로도 얼마든지 풀이가 가능합니다. 그러나, 책에 있는 풀이들은 여러가지 방식으로 시도해보고 가능하면 최적의 풀이를 고민하며 찾아낸 방식이라 그 보다 더 좋은 방법을 찾기는 쉽지 않을거 같네요.

이 풀이 또한 가장 높은 막대를 기준으로 한다는 점에서 투 포인터와 유사한 접근으로 보이는데, 책에서도 투 포인터 풀이가 있습니다. https://github.com/onlybooks/algorithm-interview/blob/master/3-linear-data-structures/ch07/8-1.py 이 풀이에 비해 코드도 길고, 시간 복잡도도 더 높아 보여요(최대 길이를 찾고, 리스트를 뒤집는 등).

좀 더 최적화를 해본다면 두 번째 리스트는 뒤집지 말고 아예 뒤에서 부터 왼쪽으로 이동하는 형태로 풀이하면 만약 입력값이 엄청나게 큰 목록이라도 좀 더 효율적으로 처리할 수 있을거 같아요.

left, right = len(right_height) - 2, len(right_height) -1
while
    if
        left -= 1
    else
        left, right = left - 1, left

이외에 다른 부분은 다 좋은거 같습니다. 알고리즘도 직관적이고 좋은 풀이네요!

[WonJongWoon]

좋은 알고리즘이네요. 수고하셨습니다.
제가 볼때는 문제 없이 잘 동작하는거 같네요.

당연한 얘기지만 책에 있는 풀이는 하나의 예 일 뿐이고 다른 방법으로도 얼마든지 풀이가 가능합니다. 그러나, 책에 있는 풀이들은 여러가지 방식으로 시도해보고 가능하면 최적의 풀이를 고민하며 찾아낸 방식이라 그 보다 더 좋은 방법을 찾기는 쉽지 않을거 같네요.

이 풀이 또한 가장 높은 막대를 기준으로 한다는 점에서 투 포인터와 유사한 접근으로 보이는데, 책에서도 투 포인터 풀이가 있습니다. https://github.com/onlybooks/algorithm-interview/blob/master/3-linear-data-structures/ch07/8-1.py 이 풀이에 비해 코드도 길고, 시간 복잡도도 더 높아 보여요(최대 길이를 찾고, 리스트를 뒤집는 등).

좀 더 최적화를 해본다면 두 번째 리스트는 뒤집지 말고 아예 뒤에서 부터 왼쪽으로 이동하는 형태로 풀이하면 만약 입력값이 엄청나게 큰 목록이라도 좀 더 효율적으로 처리할 수 있을거 같아요.

left, right = len(right_height) - 2, len(right_height) -1
while
    if
        left -= 1
    else
        left, right = left - 1, left

이외에 다른 부분은 다 좋은거 같습니다. 알고리즘도 직관적이고 좋은 풀이네요!

감사합니다. 뒤집지 않고 해볼려고했는데 잘 떠오르지 않아서 고민이였는데 한번 더 생각해보겠습니다. 책의 풀이도 열심히 보고 있습니다. 바쁘실텐데 답변 해주셔셔 감사합니다. !