<섹션3-Two pointers, Sliding window> 1. 두 배열 합치기

1. 두 배열 합치기

<설명>

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램
을 작성하세요.

<입력>

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

<출력>

오름차순으로 정렬된 배열을 출력합니다.

===================================================

<코드>

시간복잡도를 줄이기 위해 for문이 아닌 while문을 활용한다. 두 배열의 값들이 모두 있을 때는 둘을 비교하여 arraylist에 삽입한다. 한 배열이 먼저 끝날 경우도 있으므로 이를 위해 각자의 while문도 준비해야 한다.

import java.util.*;

class Main {	
	public ArrayList<Integer> solution(int num,int num2,int[] array1,int[] array2){
		ArrayList<Integer> answer=new ArrayList<>();
		int p1=0,p2=0;
		while(p1<num&&p2<num2) {
			if(array1[p1]<array2[p2]) answer.add(array1[p1++]);
			else answer.add(array2[p2++]);
		}
		while(p1<num) {
			 answer.add(array1[p1++]);
		}
		while(p2<num2) {
			answer.add(array2[p2++]);
		}
		return answer;
		
	}
		
		
	public static void main(String[] args) {
		Main main = new Main();
		Scanner scan = new Scanner(System.in);
	   
		int num=scan.nextInt();
	    int[] array1=new int[num];
		for(int i=0;i<num;i++) {
			array1[i]=scan.nextInt();
			}
		
	    int num2=scan.nextInt();
		int[] array2=new int[num2];
		for(int i=0;i<num2;i++) {
			array2[i]=scan.nextInt();
			}
		
		for(int x: main.solution(num,num2,array1,array2)) {
		System.out.print(x+" ");}
		}
}

<중요>

1) 시간복잡도를 줄이기 위해 while문을 활용할 것