3-1 두 배열 합치기 (Java)

✏️ 문제

---

설명

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

입력

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.

세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.

네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.

각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

출력

오름차순으로 정렬된 배열을 출력합니다.

예제입력
3
1 3 5
5
2 3 6 7 9

예제출력
1 2 3 3 5 6 7 9

---

✏️ 코드

two pointers 배우기 전

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

// 안좋은 방법
class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int [] arr = new int[N];
        for (int i=0; i<N; i++) {
            arr[i] = sc.nextInt();
        }
        int M = sc.nextInt();
        int [] arr1 = new int[M];
        for (int i=0; i<M; i++) {
            arr1[i] = sc.nextInt();
        }
        
        sc.close();

        for (int i : solution(arr, arr1)) {
            System.out.print(i + " ");
        }
    }

    public static ArrayList<Integer> solution(int[] arr, int[] arr1) {
        ArrayList<Integer> answer = new ArrayList<Integer>();
        for (int i=0; i<arr.length; i++) {
            answer.add(arr[i]);
        }
        for (int i=0; i<arr1.length; i++) {
            answer.add(arr1[i]);
        }
        Collections.sort(answer);
        return answer;
    }
}

투포인터 알고리즘 적용 전에 ArrayList에 다 담고 정렬하는 방식으로 사용했다. 이렇게 되면 시간 복잡도에서 효율적이지 못하다.

class twopointers {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [] arr = new int[n];
        for (int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int [] arr1 = new int[m];
        for (int i=0; i<m; i++) {
            arr1[i] = sc.nextInt();
        }
        sc.close();
        for (int i : solution(n, m, arr, arr1)) {
            System.out.print(i + " ");
        }
    }

    public static ArrayList<Integer> solution(int n, int m, int[] arr, int[] arr1) {
        ArrayList<Integer> answer = new ArrayList<Integer>();
        int p1 = 0; 
        int p2 = 0;
    
        while (p1<n && p2<m) {
            if (arr[p1] < arr1[p2]) {
                answer.add(arr[p1++]);
            }
            else {
                answer.add(arr1[p2++]);
            }
        }
        
        while (p1<n) {
            answer.add(arr[p1++]);
        }

        while (p2<m) {
            answer.add(arr1[p2++]);
        }

        return answer;
    }
}

arr, arr1 배열에 각각 해당하는 포인터 p1, p2가 있다.
p1, p2 는 배열을 탐색하면서 서로 비교하며 작은 값을 ArrayList에 담아준다. 그렇게 반복하다 둘 중 하나의 배열이 탐색을 끝나게 된다.

탐색이 끝난 배열이 있다면 남은 배열은 그대로 있는 값을 넣어주면 된다. 입력을 오름차순으로 받았기 때문이다.

---

정리