투 포인터(Two Pointers) 알고리즘은 주로 순차적 접근이 요구되는 조건 등의 특수한 경우에 사용되는 알고리즘입니다.
예를 들면, 정렬된 두 배열이 주어질 때 두 배열을 하나의 정렬된 배열로 합치는 경우, 어떤 배열의 연속 부분집합(contiguous subarray)의 원소의 합이 k인 경우의 수를 찾는 경우 등이 있습니다.
투 포인터 알고리즘의 기본 동작원리는 이름 그대로 두 개의 지점(포인터)를 옮겨가면서 구하고자 하는 답을 구하는 것입니다.
정렬된 두 개의 배열 A, B가 주어집니다. 이를 정렬된 하나의 배열로 합치는 문제를 투 포인터 알고리즘으로 해결해보겠습니다.
이미 정렬이 되었기 때문에, 각 배열의 0번지는 각 배열의 최솟값이 있습니다.
합친 배열의 0번지에는 A[0]과 B[0]중 작은 값이 들어가게 됩니다.
합친 배열의 0번지에 -3이 들어갔습니다.
그다음 작은 값을 비교할 때는 A에서는 0번지를, B에서는 0번지를 사용하였기 때문에 1번지를 비교하여야 합니다.
합친 배열의 1번지에는 A의 0번지가 들어갔습니다.
이제 남은 A배열의 가장 작은 값인 A[1]과 B배열의 가장 작은 값인 B[1]을 비교하는 방식으로 계속 진행을 합니다.
이렇게 진행하다 보면, 위와 같은 상황이 오게 됩니다.
이 경우에는 A의 모든 값이 B[4]보다 작기 때문에 남은 배열에는 B값을 차례대로 넣어주면 됩니다.
구현 시 위와 같은 상황에도 동작할 수 있도록 정확한 처리가 필요하며, 첨자 실수가 많이 나올 수 있는 부분이므로 유의하여 작성합니다.
완전히 처리된 결과입니다. 이 알고리즘을 쓰는 이유는 시간 복잡도 때문입니다.
물론, 두 배열을 이어(catenate) 정렬한다면 O((N+M) log (N+M))에 해결을 할 수 있지만, 위의 알고리즘을 사용하면 A배열의 포인터가 한번 순회, B배열의 포인터가 한번 순회로 총 O(N+M)이 나오므로 효율적입니다.
어떤 자연수만 있는 배열의 부분 연속합이 k가 되는 경우의 수를 구하는 문제 또한 하나의 배열에 두 개의 포인터(왼쪽, 오른쪽)를 지정하면 쉽게 해결 가능합니다.
SUM[L, R] < k 일 때, R을 증가시켜주어 k에 근접할 수 있도록 범위를 넓혀주며
SUM[L, R] > k 일 때, L을 증가시켜주어 범위를 좁혀주며
SUM[L, R] == k 일 때는 정답을 카운트해주며 다음 경우를 찾기 위해 다시 L을 증가시켜주어 범위를 좁혀줍니다.
이 알고리즘 또한 두 포인터가 하나의 배열을 두 번 탐색하는 것과 같으므로 시간복잡도는 O(N)으로 빠르게 동작합니다.
특수한 상황에서 적용 가능한 알고리즘이지만, 동작속도가 빠르므로 유용하게 쓰입니다.
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
ArrayList<Integer> A = new ArrayList<>();
for (int i = 0; i < n; i++)
A.add(scanner.nextInt());
int m = scanner.nextInt();
ArrayList<Integer> B = new ArrayList<>();
for (int i = 0; i < m; i++)
B.add(scanner.nextInt());
ArrayList<Integer> Sorted = new ArrayList<>();
int a = 0, b = 0;
for (int i = 0; i < n + m; i++) {
if (b == m || (b != m && a < n && A.get(a) < B.get(b)))
Sorted.add(A.get(a++));
else
Sorted.add(B.get(b++));
}
for (int x : Sorted)
System.out.print(x + " ");
}
}