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

[WonJongWoon]

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

[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

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

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