11. Container With Most Water

🎰 문제

문제는 다음과 같다. 인자로 주어지는 height값은 숫자들로 이루어진 배열이고 그래프에서 y축(높이)를 나타내고 있다.

위와 같은 배열을 그래프로 옮겼을 경우 물을 담을 수 있는 가장 넓은 면적의 넓비 값을 반환해 주세요.

🧩 생각 1

그림과 같은 예시의 배열은 [1, 8, 6, 2, 5, 4, 8, 3, 7]이다. 제일 처음으로 한 생각은 이중 for문의 형식으로 배열의 첫번째 인덱스를 반복문을 돌게한 후, 그 내부에서 하나씩 다음 인덱스부터 인덱스 값을 1씩 증가해간다. 모든 경우의 수를 다 통과해가며 그 값을 max()를 통해 비교해가며 저장을 하여 최대값을 구하는 방법이였다.

1. 가장 큰 고정 인덱스
2. 고정 인덱스 다음 인덱스부터 차례차례 1씩 증가시키며 비교
3. 인덱스 값이 증가 할때 마다 넓이값을 구해 max()를 통해 비교

위와 같은 코드가 나온다.

❌ 생각 1의 문제점

위와 같이 작성하면 결과값은 일치하게 나오지만 for문이 두번 사용되었기 때문에 시간 복잡도가 O(n^2)로 제곱의 형태로 나와 좋지 못하였다.

🧩 생각 2

그러다 생각이 난 것이 전에 얼핏 들었었던 양 쪽 끝점부터의 비교였다. 쉽게 정리하자면 0번 인덱스와 마지막 인덱스의 값을 초기값으로 잡고 비교해 나가는 방식이다.

1. 양 쪽 끝 인덱스를 초기값으로 저장
2. 그 사이의 넓이 값을 구한다.
3. 양 쪽 값을 비교하여 왼쪽이 작으면 하나 증가시키고 오른쪽이 작으면 하나 감소시킨다.

🎯 해결

위와 같이 진행하면 반복문을 한번만 사용해서 진행할 수 있다. 반복문을 무조건적으로 for문이 아닌 while문을 사용할 수도 있고 상황에 따라서 알맞게 사용하는 것이 맞는거 같다. 여기서 사용하는 알고리즘은 two point 알고리즘이라고 부른다. 간단하게 설명하자면 양쪽부터 시작해가며 비교해가며 하나하나 줄여나아가는 방식이다.