til/Algorithm
[Two pointers] 두 배열 합치기
값진
2021. 7. 27. 23:24
오름차순 정렬된 두 배열이 주어지면, 오름차순으로 합쳐 출력하는 프로그램
입력
3
1 3 5
5
2 3 6 7 9
출력
1 2 3 3 5 6 7 9
import java.util.*;
class Main {
public ArrayList<Integer> solution(int n, int m, int[] a, int[] b){
ArrayList<Integer> answer = new ArrayList<>();
int p1=0, p2=0;
while(p1<n && p2<m){
if(a[p1]<b[p2]) answer.add(a[p1++]); //p1이 가리키는 값이 먼저 add 되고 그 다음 p1증가
else answer.add(b[p2++]);
}
//둘 중 남은 쪽 배열 합쳐주기
while(p1<n) answer.add(a[p1++]);
while(p2<m) answer.add(b[p2++]);
return answer;
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int[] a=new int[n];
for(int i=0; i<n; i++){
a[i]=kb.nextInt();
}
int m=kb.nextInt();
int[] b=new int[m];
for(int i=0; i<m; i++){
b[i]=kb.nextInt();
}
for(int x : T.solution(n, m, a, b)) System.out.print(x+" ");
}
}
a[p1] < b[p2]
작은 쪽의 값을 answer에 넣고, 넣은 값의 포인터는 1 증가
예 ) 1과 2 비교->1넣기, 3과 2 비교 ->2넣기
a배열 n개, b배열 m개면 p1<n p2<m 이어야함
answer.add(a[++p1]); 이었다면 p1이 우선 증가되고 난 후 p1이 가리키는 값이 add된다