<3.1> 두배열 합치기 - Two Pointers Algorithm

문제
: 오름차순으로 정렬된 두 배열이 입력되면 , 두 배열을 오름차순으로 합쳐 하나의 배열로 출력하는 프로그램을 작성하라.
(이때 각 배열의 원소가 입력되기 전 각 배열의 사이즈인 N,M이 먼저 입력되고 ,
이때 N,M은 1이상 100이하의 자연수 이다.)

이 문제의 요구사항은 주어진 그대로 , 두 배열을 합치되 - 오름차순을 유지하면서 합치는 것이다.

이에 따른 해결 로직은 다양하게 생각할 수 있겠지만,
문제에서 의도하고 있는 방법은 바로 two pointers 알고리즘을 사용하는 것이다.

[two pointers 알고리즘]
: 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘
(https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0)

결국 핵심은 배열의 element를 가리킬 수 있는 Pointer를 이용하는 것이고,
우리의 문제에서는 2개의 배열이 주어지므로 - 2개의 Pointer를 사용하여 - 각 배열의 element를 가리키는 방식으로 문제를 해결해야 한다.

[해결 로직]

• 먼저 입력으로 주어지는 두 배열이 오름차순으로 정렬된 상태로 입력되기 때문에,
  두 배열의 정렬된 element들 중 각 최솟값만을 비교하여 - 결과 배열에 대입하기를 반복하면 - 오름차순을 유지하면서 두 배열을 합칠 수 있다.
• 그리고 이때 각 배열의 최솟값을 가리키기 위해 Pointer가 사용된다!

• 각각의 Pointer는 0 값을 가져 - arr1[0] 즉 0번 element부터 가리키기 시작하고 ,
  1씩 증가되면서 - 그 다음 최솟값을 가리키게 된다.
• 이러한 방식으로 먼저 2개의 Pointer 중 한 Pointer값이 각 배열의 size에 도달할 때 까지
  arr1[p1]와 arr2[p2] 값을 비교하면서 - 더 작은값을 결과 배열에 대입한다.
• 이후 두 Pointer중 한 Pointer가 그 배열의 size에 도달했다면 - arr1과 arr2 중 하나는 다 비워졌다는 뜻 이므로 - 비워지지 않은 남은 배열을 찾아 - 결과배열에 순차 대입 해주면 된다.

위 로직에 따라 구현한 코드는 아래와 같다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int[] solution(int[] arr1 , int size1, int[] arr2, int size2){
        int pointer1 = 0;
        int pointer2 = 0;
        int pointer3 = 0;

        int[] arr = new int[size1+size2];

        while(pointer1<size1 && pointer2<size2){
            if(arr1[pointer1] < arr2[pointer2])
                arr[pointer3++] = arr1[pointer1++];
            else
                arr[pointer3++] = arr2[pointer2++];
        }

        while(pointer1 < size1){
            arr[pointer3++] = arr1[pointer1++];
        }

        while(pointer2 < size2){
            arr[pointer3++] = arr2[pointer2++];
        }

        return arr;
    }

    public static void main(String[] args) {

        //0. Scanner 준비
        Scanner sc = new Scanner(System.in);

        //1. 두 배열 입력
        int size1 = sc.nextInt();
        int[] arr1 = new int[size1];
        for(int i=0; i<size1; i++){
            arr1[i] = sc.nextInt();
        }

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

        //2. 두 배열을 인자로 넘기면서 solution() 호출 -> solution()에서 two pointer Algorithm을 써서 배열을 하나로 합친뒤 반환
        int[] arr3 = solution(arr1, size1, arr2, size2);

        //3. 반환된 배열을 출력
        Arrays.stream(arr3)
                .forEach(e -> System.out.print(e + " "));
    }
}

[이 문제에서 기억할 점]
: 1차원 배열에 대하여 element를 가리켜가면서 문제를 해결해야 할 경우,
이 Two Pointers 알고리즘을 사용해야 한다는 점을 기억하자!

즉 무조건 합쳐서 다시 정렬하는 O(n * log n) 의 시간복잡도로 풀지 말고
(가장 빠른 퀵정렬도 O(n x log n))
투포인터 알고리즘을 써서 O(n) 로 풀어라

• 결국 투포인터 알고리즘은 O(n * log n) 의 시간복잡도를 O(n)의 시간복잡도로 풀 수 있도록 만들어주는 알고리즘!