[LeetCode] 11. Container With Most Water (C++)

문제

 

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

Container With Most Water - LeetCode

 

풀이

 

난이도: Medium 

 

훨씬 간단한 스위핑 풀이가 있지만 정렬을 이용한 본인의 풀이부터 소개하겠다.

 

 

정렬을 이용한 풀이 O(n log(n))

 

pair<int,int> 자료구조를 이용하여 firt에는 높이, second에는 위치 값을 저장한 다음 높이를 내림차순으로 정렬해주자.

그리고 가장 높은 두 기둥의 값을 가져와 container의 왼쪽(left)과 오른쪽(right) 기둥으로 설정한다.

 

이제 높은 기둥의 순서대로 다음 기둥으로 선택해 다음을 확인해보자.

 

다음 기둥의 위치가 left 기둥보다 왼쪽 또는 right기둥보다 오른쪽에 있는 경우

넓이를 결정하는 것은 두 기둥 중에 짧은 기둥의 높이 이므로, container의 높이 짧아졌다면 적어도 너비는 길어져야 최댓값이 될 수 있다.

따라서 다음 기둥은 left 기둥보다 왼쪽에 있거나 right보다 오른쪽에 있어야 너비가 늘어난다.

다음 기둥의 위치가 left와 right 사이에 있는 경우는

높이가 높아지지도, 너비가 늘어나지 않으므로 계산할 필요가 없다.

 

left보다 왼쪽에 있다면 새로운 left기둥으로, right보다 오른쪽에 있다면 새로운 right기둥으로 설정하여 형성되는 새로운 container의 넓이를 비교하면 된다.

 

이런 경우, 다음과 같이 새로운 왼쪽 기둥이 현재의 left와 이루는 너비가 더 클 수 있지 않나라고 생각할 수 있다.

하지만 당연하게도 내림차순으로 정렬된 상태에서 새로운 기둥은 현재의 left, right기둥보다 작거나 같기 때문에 항상 container의 높이는 새로운 기둥의 높이로 설정된다.

따라서 너비를 더 늘릴 수 있는 경우만 항상 답이 될 수 있다.

 

이러한 풀이는 정렬 후는 스위핑으로 O(n)에 해결이 되지만, 정렬의 복잡도가 O(n log(n))이므로 정렬의 복잡도에 지배된다.

 

 

더 간단한 풀이 O(n)

 

사실 정렬없이 스위핑만으로 해결이 가능하다.

이번에는 배열의 양 끝을 left, right로 설정하여 시작한다.

위의 풀이에서는 너비를 늘릴 수 있을 때만 계산을 진행했다면, 이번에는 높이를 높일 수 있는 경우만 진행한다.

이는 계산을 최대 너비에서 시작하기 때문에 이보다 더 넓은 container가 되려면 적어도 높이가 더 높아야 되기 때문이다.

따라서 left와 right를 줄여가면서 현재 설정된 container의 높이(h) 보다 더 큰 기둥들만 새로운 기둥이 될 수 있도록 고려해준다.

자세한 코드는 아래의 게시글을 참조하자.

 

 

참고 풀이: Simple and fast C++/C with explanation

 

+LeetCode에서는 간단하게 풀이와 더 빠른 방법을 토론하는 곳이 있어서 정말 편리하다.

백준에도 있다면 참 좋겠지만, 문제수는 적지만 깔끔한 문제가 많은 LeetCode에서 밖에 적용하기 힘들어 보이긴 한다.

 

코드 

정렬을 사용한 코드입니다.