Algorithm

투포인터 알고리즘

일반적으로 이중 for 문을 통해서 O(n^2) 시간 복잡도에 푸는 문제를 투포인터를 활용하면 O(n) 시간 복잡도로 풀 수 있다.

투포인터 알고리즘은 주로 배열이 정렬되어 있을 때 사용된다.

투포인터 알고리즘의 핵심은 이전 결과를 활용하는 것에 있다.

예를 들어 기존에는 i,j 두 개의 변수로 이중 for 문을 돌 때는 i = 0 일 때 j를 처음부터 끝까지 확인하고, i = 1 일 때도 j를 처음부터 끝까지 확인한다.

투포인터에서는 i = 0 일 때의 정보를 i = 1 일 때 활용하여 시간 복잡도를 줄인다.

만약 배열이 오름차순으로 정렬되어 있다면 i = 0 일 때의 값은 i = 1 일 때보다 작을 것이다. 이러한 값은 크고 작음을 활용하여 이전의 값을 활용하는 것이다.

하지만 배열이 정렬되어 있지 않다면 i = 0 일 때와 i = 1 일 때 값의 관계를 모르기 때문에 이전의 값을 활용하기 어렵다.

해당 문제를 일반적으로 생각했을 때는 O(n^3) 시간 복잡도로 풀 수 있을 것이다.

하지만 그러면 시간 초과가 발생하기 때문에 투포인터를 활용하여 시간 복잡도를 한 단계 줄여보자.

위 문제에서 원하는 값은 배열의 값이다. 배열의 인덱스가 아니다. 따라서 배열을 정렬하여도 답을 찾는데는 문제가 없다.

그렇다면 어떻게 풀어야 할까?

일반적인 투포인터 문제에서 배열 내 두 값의 합이 0인 원소를 찾는 문제로 생각해보면 답이 보인다.

대신 해당 문제는 3개의 원소의 합을 물어보기 때문에 하나의 원소 값을 고정 시켜두고 나머지 2개의 원소를 조정하여 고정한 값과 더했을 때 0이 되는 원소들을 찾으면 된다.

그렇다면 고정시킬 원소가 n개 존재할 것이고, 나머지 n-1개의 원소에서 투포인터를 이용하여 원소를 찾는다.

이때의 시간복잡도는 O(n^2)이 될 것이다.

유의할 점

해당 문제에서 투포인터를 설정할 때는 j를 배열의 앞에서부터 k를 배열의 뒤에서 부터 설정해야한다.

이렇게 하면 세 원소의 합을 비교했을 때