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

문제 원문 링크 : https://leetcode.com/problems/container-with-most-water/

Container With Most Water - LeetCode

얼핏 보면

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

문제와 비슷하다.

그래서 맨 처음에 아무 생각없이 위 문제와 같은 방법으로 접근했더니 역시나 Wrong Answer! 문제 제대로 읽자.

 

일단 가장 먼저 떠오르는 방법인 Brute Force(완전 탐색)으로 접근해보자.

 

이것 역시나 정답은 아니었다.

 

이런 무지막지하게 긴 input이 있기 때문이다.

---

모든 경우의 수를 다 탐색하지 않는 접근법이 있을까?

 

각 블럭에서 가장 크게 만들 수 있는 컨테이너는 해당 블럭을 기준으로,

1. 가장 멀리 떨어져있으면서(= 가로 길이가 가장 길면서) 2. 높이가 크거나 같은 블럭과 만들게 되는 컨테이너이다.

 

그렇다면 양 끝에서부터 시작해서 어떤 블럭보다 큰 블럭이 나오면 그 블럭을 이용해 곧장 넓이를 구하고,

찾은 후에는 하나씩 안쪽으로 범위를 좁혀가면서 다른 블럭에 대해서도 넓이를 구하고 그 중에 최대를 취하면 되지 않을까?

 

이 접근 방식은 O(n)으로, Brute Force의 O(n^2)보다 훨씬 빠른 알고리즘이다.

 

코드를 구현하면 아래와 같다.

---

Code

https://github.com/changyeon2/Algorithm/blob/master/leetcode/problem%2011/C%2B%2B/solution%201.cpp