투 포인터 알고리즘
Two Pointers 말 그대로 각자 다른 원소를 가리키고 있는 포인터 2개를 가지고 배열을 각각 순회하며 원하는 값을 얻는 알고리즘 풀이 방식이다. 절대 정답이 되지 않는 경우를 Skip할 수 있기 때문에 이중 포문보다 훨씬 효율적이다.(현재 포인터가 가리킨 지점 이후로는 정답이 될 수 없다면 순회를 종료 할 수있음!)
시간 복잡도
배열 1에서 포인터를 n번 움직이고, 배열 2에서 포인터를 m번 움직이니까 시간 복잡도는 O(n+m) 를 가진다. 보통 두 배열을 받아 공통된 값을 answer에 push 해서 리턴하는 식의 문제에서는 이중 for 문을 써서 문제를 해결하기 쉬운데, 이중 루프의 시간 복잡도는 O(n²)을 가지기 때문에 투 포인터 알고리즘으로 처리하는게 효율적이다!👍
문제 예시
- A, B 두 개의 집합이 주어질 때 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 경우
- 오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 경우
풀이 예시
- 배열 각각에 포인터를 index 0에 위치 시킨다.
- while 이용해서 포인터가 배열 길이보다 작을 동안 주어진 포인터를 순회시키며 문제의 조건에 일치하는 요소를 answer에 push 시킨다.
- 2번에서 적용시킨 while문을 빠져나온 뒤 후속 처리는 해준다.(요소가 남아있는 배열의 요소들을 모두 answer에 push 한다 던지..)
