[Java-투포인터] 두 배열 합쳐서 정렬하기

투 포인터를 이용해 두 개의 배열을 하나의 정렬된 배열로 합치는 문제는 추가 정렬 없이 O(N)의 시간 복잡도로 문제를 해결할 수 있다.

문제 상황

다음과 같이 이미 오름차순으로 정렬된 두 배열이 주어진다.

3
1 3 5
5
2 3 6 7 9

투 포인터란?

투 포인터 기법은 두 개의 포인터(인덱스)를 사용하여 배열을 순회하는 방식이다.

• p1: 첫 번째 배열(arr1)의 현재 위치
• p2: 두 번째 배열(arr2)의 현재 위치

각 포인터는 자신이 가리키는 값이 처리되면 한 칸씩 앞으로 이동한다.

1단계

둘 중 작은 값인 p1의 위치인 값을 result에 추가한 후, p1을 증가시킨다.

2단계

둘 중 작은 값인 p2의 위치인 값을 result에 추가 후, p2를 증가시킨다.

마찬가지로 아래의 단계 모두 같은 방식으로 동작한다.

3단계

4단계

5단계

 

 

전체 코드

class Solution {

    public ArrayList<Integer> solution(int n, int m, int[] arr1, int[] arr2) {
        ArrayList<Integer> answer = new ArrayList<Integer>();

        int p1 = 0, p2 = 0;
        while (p1 < n && p2 < m) {
            if (arr1[p1] < arr2[p2]) {
                answer.add(arr1[p1++]);
            } else {
                answer.add(arr2[p2++]);
            }
        }
		
        // 남은 p1이나 p2가 있다면 추가
        while (p1 < n)
            answer.add(arr1[p1++]);
        while (p2 < m)
            answer.add(arr2[p2++]);

        return answer;
    }

    public static void main(String[] args) throws Exception {

        Solution T = new Solution();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr1 = new int[n];
        String[] split = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr1[i] = Integer.parseInt(split[i]);
        }

        int m = Integer.parseInt(br.readLine());
        int[] arr2 = new int[m];
        split = br.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            arr2[i] = Integer.parseInt(split[i]);
        }

        for (int x : T.solution(n, m, arr1, arr2)) {
            System.out.print(x + " ");
        }

    }

}