Trapping Rain Water 문제 내용 Stones가 쌓여있는 길이 Arrays가 주어졌을 때 Stones 사이에 얼마나 많은 물이 쌓일 수 있는가? 풀이 방법 풀이 방법은 여러가지가 있을 수 있는데 가장 쉬운 방법은 왼쪽에서 부터 포지션을 하나씩 늘려가면서, 현재 포지션의 왼쪽과 오른쪽을 Full Search한 후 왼쪽과 오른쪽의 가장 높은 높이를 찾고 그중 낮은 값을 답으로 하면된다. 상기 그림을 보면 왼쪽 포지션과 오른쪽 포지션을 보고 가장 낮은 포지션의 값인 2을 현재 포지션의 물 높이로 선택 하면 된다. 그런데 이렇게 full search 하게 되면 Height의 Size N 만큼 왼쪽으로 움직일 때마다 (N-1) 만큼의 Search가 매번 필요하다. 수식으로 하면 O(N*(N-1))이 ..