두 배열 합치기(Two Pointers)

풀기 앞서,
Two Pointer 란?
문자 그대로, 두개의 포인터를 이용해서 알고리즘을 풀어나가는 방식이다.
Two pointers 풀이방식은 O(N)의 시간만 가지고 풀어낼 수 있다.

문제

나의풀이

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++]);
				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를 각각 만들어주고
while문으로 탐색을 시작한다.

a[p1]과 b[p2]를 비교해서 더 작은 값을 answer에 넣고,
추가된곳의 포인터는 다음을 가리켜야하므로 1증가된다.

이런식으로 answer에 배열이 끝날때까지 담기면, 정렬이 되는데
배열 길이가 다르다면 남은 배열의 원소들을 다 추가해줘야 한다.

이때도 추가한 후에는 포인터값이 1증가시켜 끝나지않은 배열을 끝나게 while문을 돌려야한다.

핵심키워드

후위연산자

while(p1<n) answer.add(a[p1++]);
이렇게 나타낸다면 answer에는 p1값이 담긴 후 p1의 값이 1 증가한다.

전위연산자

while(p1<n) answer.add(a[++p1]);
이렇게 나타낸다면 answer에 p1의 값이 담기기전 p1이 1 증가한다.

항상 answer.add(a); 를 한 후에 다음줄에 p1++; 이런식으로 증가를 시켜줬는데, 이 방법도 기억하고 애용해야겠다!