[알고리즘] 03.Two pointers, Sliding window[효율성 : O(n^2)–>O(n)] / 1. 두 배열 합치기

두 배열 합치기

설명

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

입력

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

출력

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

예시 입력 1

3
1 3 5
5
2 3 6 7 9

예시 출력 1

1 2 3 3 5 6 7 9

코드

import java.util.ArrayList;

public class Main {

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int[] arrA = new int[a];
		for(int i = 0; i<a; i++) {
			arrA[i] = sc.nextInt();
		}

		int b = sc.nextInt();
		int[] arrB = new int[b];
		for(int i = 0; i<b; i++) {
			arrB[i] = sc.nextInt();
		}

		for(int x : T.solution(a, arrA, b, arrB)) {
			System.out.print(x + " ");
		}
	}


	public ArrayList<Integer> solution(int a, int[] arrA, int b, int[] arrB) {
		ArrayList<Integer> answer = new ArrayList<Integer>();

		int p1=0, p2=0;
		int cnt = a+b;

		while(cnt >0) {
			if(a>p1 && arrA[p1] <= arrB[p2]) {
				answer.add(arrA[p1]);
				p1++;
			}else {
				answer.add(arrB[p2]);
				p2++;
			}
			cnt--;
		}

		return answer;
	}
}