투포인터 알고리즘이란?
슬라이딩 윈도우라고도 불리는 이 알고리즘은 말 그대로 두 개의 포인터를 이용하여 문제를 푸는 알고리즘 기법입니다. 예제 문제를 통해 이를 보다 더 쉽게 이해하고자 합니다.
예제 문제
위 문제는 두 개의 배열이 주어졌을 때, 두 배열을 합친 후 정렬한 결과를 출력하는 문제입니다.
package baekjoon.two_pointer;
import java.util.Scanner;
public class _11728 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = new int[N];
int[] B = new int[M];
int[] answer = new int[N + M];
int aIdx = 0;
int bIdx = 0;
int idx = 0;
for (int i = 0; i < A.length; i++) {
A[i] = sc.nextInt();
}
for (int i = 0; i < B.length; i++) {
B[i] = sc.nextInt();
}
while (true) {
if (aIdx == A.length) {
while (bIdx < B.length) {
answer[idx++] = B[bIdx++];
}
break;
}
if (bIdx == B.length) {
while (aIdx < A.length) {
answer[idx++] = A[aIdx++];
}
break;
}
if (A[aIdx] < B[bIdx]) {
answer[idx++] = A[aIdx++];
} else if (A[aIdx] > B[bIdx]) {
answer[idx++] = B[bIdx++];
} else {
answer[idx++] = A[aIdx++];
}
}
for (int i = 0; i < answer.length; i++) {
System.out.print(answer[i] + " ");
}
}
}
SQL
복사
