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된다