알고리즘 문제를 풀다가 leetcode의 3Sum 문제를 푼 사람들의 코드를 봤는데 투포인터로 합이 k인 두수를 찾고있는 코드를 봐서 블로그에 정리하려고 합니다.
유명한 풀이법일수도 있는데 저는 꽤 재미있는것 같아서 따로 정리해두려고 합니다.
먼저 숫자 배열에서 투포인터를 이용해 합이 K인 두수를 찾는 방법이 있습니다.
이때 꼭 배열은 정렬되어 있어야합니다.
오름차순 정렬을 하는게 확실히 이해하기 편합니다.
이렇게 정렬된 배열이 있다고 가정하고 양 끝에 포인터를 둡니다.
이 양포인터를 좁혀가면서 합이 K인 두수를 찾을 예정입니다.
K를 15 라고 가정했을때, 20+2 > 15 입니다.
따라서 20이 제일 큰수 이므로 20과 왼쪽 어느수를 조합하든 15보다 큰수가 될것이라는 명제가 성립됩니다.
그렇다면 20이라는 수를 배제하고 진행할 수 있습니다.
이것이 투포인터의 원리입니다.
따라서 20에 있던 포인터를 왼쪽으로 옮길수 있습니다. 이때도 두 수의 합이 15보다 크므로 18또한 배제하고 진행할수 있습니다. 20이 없어졌으니 18이 가장 큰 수가 되었다고 생각하면 이해하기 쉽습니다. 그 다음 수인 17도 합이 15보다 크므로 배제합니다.
11의 경우 11+2 < 15 이므로 여기선 가장 작은수인 2를 기준으로 생각해보면 오른쪽 어떤수를 더해도 15보다 작을 것입니다. 그러므로 2를 배제하고 그다음수인 4로 포인터를 옮길 수 있습니다. (4가 가장 작은 수가 됩니다.)
🎉 짜잔!~ 합이 15인 답을 찾을 수 있었습니다.
이런 식으로 굳이 확인할 필요가 없는 경우의 수를 스킵해서 완전검색보다 더 빨리 두 수를 찾을 수 있습니다.
만약 두 포인터가 엇갈려서 leftPointerIdx > rightPointerIdx 이렇게 된다면 그 배열에는 합이 K인 두수의 조합이 없다고 생각하면 됩니다.
두 포인터가 한번 루프돌때마다 1만큼 배열의 길이 안에서 움직이므로 O(N)의 시간복잡도를 가집니다.
