[알고리즘]Two pointers - 두 배열 합치기

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

입력) 첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
출력) 오름차순으로 정렬된 배열을 출력합니다.

 

참고) Two pointers

시간 복잡도 : O(N)

 

 

1)

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	public static ArrayList<Integer> solution(int n, int m, int[] a, int[] b) {
		ArrayList<Integer> answer = new ArrayList<>();
		int p1 = 0, p2 = 0; // pointers
        
		while (p1<n && p2<m) {
			if (a[p1]<b[p2]) answer.add(a[p1++]); // add 후 p1값 1 증가(후위 증감 연산자)
			else answer.add(b[p2++]);			
		}
		while (p1<n) answer.add(a[p1++]); // a 배열에 값이 남아 있을 때
		while (p2<m) answer.add(b[p2++]); // b 배열에 값이 남아 있을 때
        
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] a = new int[n];
		for (int i=0; i<n; i++) {
			a[i] = scanner.nextInt();
		}
		int m = scanner.nextInt();
		int[] b = new int[m];
		for (int i=0; i<m; i++) {
			b[i] = scanner.nextInt();
		}
		for (int x : solution(n, m, a, b)) {
			System.out.print(x + " ");
		}
	}

}

 

2)

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	public static ArrayList<Integer> solution(int n, int m, int[] a, int[] b) {
		ArrayList<Integer> answer = new ArrayList<>();
		int p1 = 0, p2 = 0; // pointers
		
		while (p1<n || p2<m) {
			if (p1==n) { // a 배열 끝
				answer.add(b[p2]);
				p2++;
			} else if (p2==m) { // b 배열 끝
				answer.add(a[p1]);
				p1++;
			} else {
				int min = Math.min(a[p1], b[p2]);
				answer.add(min);
				if (min==a[p1]) p1++;
				else p2++;
			}	
		}
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] a = new int[n];
		for (int i=0; i<n; i++) {
			a[i] = scanner.nextInt();
		}
		int m = scanner.nextInt();
		int[] b = new int[m];
		for (int i=0; i<m; i++) {
			b[i] = scanner.nextInt();
		}
		for (int x : solution(n, m, a, b)) {
			System.out.print(x + " ");
		}
	}

}

// cf) ArrayList - sort() 메소드 이용

오름차순 -> ArrayList명.sort(Comparator.naturalOrder());

내림차순 -> ArrayList명.sort(Comparator.reverseOrder());

---

결과