두 개의 포인터 변수를 통해 문제를 해결하는 알고리즘
주로 그림 처럼 두 개의 배열에 순차적으로 접근 해야 할 때 두 개의 포인터 위치를 기록 하며 처리 하는 기법입니다.
오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램 을 작성하세요.
첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다. 네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.
오름차순으로 정렬된 배열을 출력합니다.
3
1 3 5
5
2 3 6 7 9
1 2 3 3 5 6 7 9
두 개의 배열이 입력으로 주어졌을 때, 그 배열의 값들을 기록하기 위한 포인터 변수(p1, p2)를 두고 각각 0으로 초기화 합니다.
그리고 arr1, arr2를 비교하게 되는데, 포인터 변수 값인 0번의 값을 서로 비교하여 더 작은 값을 answer에 추가 합니다.
arr1[0]은 1, arr2[0]은 2이기에 arr1이 더 작으므로 answer에 추가되고 p1의 포인터 변수가 1 증가 합니다.
p1이 1 p2가 0인 상태에서 다시 비교를 시작합니다. arr1[1]은 3이고 arr2[0]은 2이므로 2가 더 작기 때문에 arr2에 있는 2가 answer에 들어가고 p2가 1 증가 합니다.
이렇게 계속 비교하다보면 arr1을 모두 순회하게 되는데, 두 배열 중 하나라도 순회가 종료되면 남아있는 배열의 값들을 모두 순회하여 그대로 answer에 추가 합니다.
function solution(A, B) {
// 두 포인터 변수 p1, p2를 0으로 초기화
let p1 = 0;
let p2 = 0;
let n = A.length;
let m = B.length;
let answer = [];
// 포인터 변수가 각각 n, m 보다 커질 경우 종료
while (p1 < n && p2 < m) {
// 만약 A보다 B에 있는 값이 더 클 경우 A에 있는 값을 answer에 추가 후 p1 1증가(후위 증가)
if (A[p1] <= B[p2]) answer.push(A[p1++]);
// 만약 A가 더 클 경우 B에 있는 값을 answer에 추가 후 p2 1증가
else answer.push(B[p2++]);
}
// 만약 A에서 answer에 추가 되어야 할 값이 있다면 마저 추가
while (p1 < n) answer.push(A[p1++]);
// 만약 B에서 answer에 추가 되어야 할 값이 있다면 마저 추가
while (p2 < m) answer.push(B[p2++]);
return answer;
}
console.log(solution([1, 3, 5], [2, 3, 6, 7, 9]));