[Java] two pointers 알고리즘

설명

리스트에 순차적으로 접근할 때 두개의 포인터를 사용하여 접근하며 처리하는 방식.
정렬되어 있는 두 리스트에서도 사용됨.

문제

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

풀이

각 배열에 포인터를 설정하고 두 포인터중에 작은 것을 먼저 넣고 둘 중에 하나의 배열이 끝나는 시점에 while문을 종료한다.
이후 두 배열 중에서 남은 배열 원소가 있을 수 있기 때문에 두 배열을 각각 while문을 돌리면서 순서대로 넣어준다.
이 문제를 풀려면 두 배열이 오름차순 정렬이 되어있어야만 한다.

코드

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

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 solution = new Main();
        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.solution(n, m, a, b)) {
            System.out.print(x + " ");
        }
    }
}