배열에서 연산의 최댓값 혹은 최솟값을 가지는 2개의 값 찾기 문제 (Two Pointers)

코딩 문제

 int 배열이 주어졌을 때, 합이 최대가 되는 2가지 Element를 찾아라. (합 연산이 곱셈, 뺄셈 등의 연산으로 바뀔수도 있고, 각 연산 외에 또다른 연산 방법을 적용한 것일 수도 있다. 연산의 종류와 관계 없이 배열에서 특정 연산의 최댓값 or 최솟값을 찾는 2가지 Element를 찾아야 하는 문제로 추상화 가능하다.)

 

이번 글을 정리하게 된 이유는 아래 문제 때문이다. (LeetCode 11. Container With Most Water)

https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=leetcode-75 

Container With Most Water - LeetCode

 

원리

 이 부류의 문제를 Two Pointers라고 한다. 메모리 주소를 가리키는 포인터 변수를 쓰는 것은 아니고 배열의 Element에 접근하는 2개의 Idx 값을 쓰기 때문에 붙여진 명칭이다. 각 Idx는 초기에 0번과 마지막 인덱스를 가리키고, Loop를 통해 각 idx를 이동하며 연산의 결과를 비교한다.

 

 이런 문제는 기본적으로 Brute Force를 사용해 풀 수 있다. 그러면 Time Complexity는 O(n^2)이 된다. Two Pointers를 사용하면 O(n)에 풀 수 있다.

 

 Two Pointers의 기본 원리는 배열의 첫번째와 마지막 인덱스로부터 시작하여 인덱스를 옮겨가며 연산의 최댓값 혹은 최솟값을 찾는 것이다. 이 원리가 동작하는 이유는, Loop 초기에 Boundary Condition부터 시작해 Locally 최댓값 혹은 최솟값을 가지도록 인덱스를 변경하다보면 Global 최댓값 혹은 최솟값을 찾게 된다는 것이다. 즉 중요한 것은 초기 조건이 Boundary Condition에서 시작한다는 점이다. 이 조건이 만족되어야 Locally 최댓값 혹은 최솟값을 가지는 연산이 Global 최적 값으로 수렴하게 된다.

 

예시 코드

 개념을 익히려면 위에 작성한 Leet Code 11번 문제를 풀어보면 된다.

Two Pointers 개념을 사용한 예제 코드는 다음과 같다.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int LeftIdx = 0;
		int RightIdx = height.size() - 1;
		int maxArea = 0;
		int Area = 0;

		while (LeftIdx != RightIdx)
		{
			Area = min(height[LeftIdx], height[RightIdx]) * (RightIdx - LeftIdx);

			if (Area > maxArea)
			{
				maxArea = Area;
			}
			else
			{
				// Do Nothing
			}

			if (height[LeftIdx] < height[RightIdx])
			{
				++LeftIdx;
			}
			else
			{
				--RightIdx;
			}
		}

		return maxArea;
    }
};