[LeetCode] Container With Most Water

 

문제

https://leetcode.com/problems/container-with-most-water/description/

 

 

 

해석

 

height배열에서 2개의 height를 골라 그 안에 가장 많은 양의 물을 저장하고 그 값을 구하는 것이다.

 

2가지 방법으로 풀어보겠습니다

 

 

1. 가장 Naive하게 떠오르는 방법으로는 모든 height의 index를 돌면서 최대값을 갱신하는 것입니다.

for i in range(len(height)-1):
	for j in range(i+1, len(height)):
      	  ans = max(ans, min(height[i], height[j])*(j-i))

 

 

이렇게 접근하면 문제는 너무 쉽게 풀리지만, Time Limit에 걸리게 됩니다.

height의 길이가 10^5이기 때문이져 

 

이 방법의 시간복잡도는 O(n^2)입니다,

공간복잡도는 더 새로운 리스트 할당이 없기 때문에, O(1) 상수 타임입니다.

 

그래서 생각한 2번째 방법!

 

 

2. Two Pointer

 

height의 가장 처음인 left와 가장 끝 인덱스 right로 설정을 해둡니다.

l = 0
r = len(height)-1

 

 

이제 두 인덱스의 배열 값 중 더 작은 값을 높이로, 인덱스의 차이를 너비로 생각해 직사각형의 후보답들을 구합니다.

1번과 거의 유사하죠.

 

그렇다면 이 과정을 하고 나서 l과 r은 어떻게 바꿔주어야 할까요?

 

height[l], height[r] 중 작은 값의 인덱스를 뒤 혹은 앞으로 옮겨주는 것입니다.

첫번째 예시로 이해를 해봅시다.

[1,8,6,2,5,4,8,3,7]

 

l은 0, r은 8이 초기 값입니다.

height[l] = 1, height[r] = 7 이므로, l을 뒤로 옮겨줘야 겠죠?

 

이 과정을 반복하다보면, 중간에 애매~~~한 구역을 그냥 넘어가서 답을 못찾는거 아닌가? 라는 의문이 들 수 있습니다.

예를 들어 처음에 l을 뒤로 안옮기고, r을 앞으로 옮기는 게 답 아니야?? 이런 의문!

 

 

(중요!!!!!!!!!) 하지만, 생각해봅시다 ㅎ

height[l]이 height[r]보다 작을때,

r을 앞으로 당긴다면 지금 순간보다 더 좋은 값을 기대할 수 없습니다.

설령 height[r]이 더 큰 값이더라도 l의 높이가 최소일 것이기에

값은 작아질 수 밖에 없죠

 

그러나, 작은값인 l을 뒤로 밀어본다면 현재의 값보다 안좋거나 같은 값일 수 있지만,

분명히! 지금보다 좋은 값이 나올 수 있는 잠재력이 생깁니다.

높이의 min값이 바뀔 수 있기 때문입니다.

 

따라서 Two Pointer 에서 l, r 포인터를 이동시켜줄때의 기준은 높이가 작은 쪽의 인덱스를 옮겨주는 것이 명확합니다.

 

 

이를 코드로 옮겨보면,

l = 0
r = len(height)-1
ans = 0
while l<r:
	ans = max(ans, min(height[l], height[r])*(r-1))
    if height[l] >= height[r]:
    	r -= 1
    else:
    	l += 1

 

명확하게 답을 구할 수 있습니다! 

 

시간복잡도는 리스트를 한번 훑기 때문에 O(n)이고 공간복잡도는 더 필요한 자료구조가 없기 때문에 O(1) 상수입니다.

 

 

 

약간 Greedy 글의 연장선 같은 문제였네요 ㅎ

https://driveitlikeyoustoleitt.tistory.com/entry/Greedy라는-방법론

Greedy라는 방법론

 

 

끘!!!