[Java] 두 배열 합치기 - Two-Pointers Algorithm

public class INF0301 {
    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) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

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

        INF0301 inf = new INF0301();
        ArrayList<Integer> solution = inf.solution(n, m, a, b);
        for (int i : solution) {
            System.out.printf(i + " ");
        }
    }
}

함수 사용하거나 새로운 배열에 arr1 + arr2 하는 것을 보는 문제가 아니다.

Two-Pointers Algorithm을 사용해보자.

 

풀이

while(p1 < n && p2 < m) {
    if(a[p1] < b[p2])  answer.add(a[p1++]);
    else answer.add(b[p2++]);
}

`p1` - 첫번째 배열의 자리를 가리키는 포인터

`p2` - 두번째 배열의 자리를 자리키는 포인터

1. 포인터가 각 배열의 끝자리로 가는 순간(정렬을 마친 순간) while문을 종료 시킨다.
2. 첫 번째, 두 번째 배열을 비교하면서 더 큰 숫자를 `answer` 에 add하고 후위증감연산자(++)를 사용하여 포인터를 +1 한다.

while(p1 < n) answer.add(a[p1++]);

while(p2 < m) answer.add(b[p2++]);

whilie문에서 첫 번째나, 두 번째 배열의 정렬이 끝났다면 한 쪽배열은 숫자가 남았기 때문에 남은 숫자는 뒤로 넣으면 된다. (입력이 이미 오름차순으로 됐기 때문에)

하지만 어떤 배열의 숫자가 남았는지 모르기 때문에 while문을 각각 작성한 것