Two Pointers_두 배열 합쳐서 오름차순으로 출력_two pointer

✅ 오름차순으로 정렬된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하세요

class Main {

    public ArrayList<Integer> solution(int n, int[] intArrOne, int m, int[] intArrTwo){
        ArrayList<Integer> answer= new ArrayList<>();
        int p1 = 0, p2=0;
        while(p1<n && p2<m){
            if(intArrOne[p1]< intArrTwo[p2]) answer.add(intArrOne[p1++]);
            else answer.add(intArrTwo[p2++]);
        }
        while(p1<n) answer.add(intArrOne[p1++]);
        while(p2<m) answer.add(intArrTwo[p2++]);
    return answer;
}
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int[] intArrOne = new int[n];
        for(int i=0; i<n; i++){
            intArrOne[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] intArrTwo = new int[m];
        for(int j=0; j<m; j++){
            intArrTwo[j] = sc.nextInt();
        }
        for(int x: T.solution(n, intArrOne, m, intArrTwo)){
            System.out.print(x+ " ");
        }
    }
}

//⭐️input:
// 3 //첫 번 째 배열 크기
// 1 3 5
// 5 //두 번 째 배열 크기
// 2 3 6 7 9
//⭐️output:
//1 2 3 3 5 6 7 9

1. 두 배열을 합친 후 오름차순으로 정렬하는 것은 시간 복잡도가 더 걸린다.
   
2. 두 배열의 인덱스를 가리키는 p1 = 0, p2=0를 만든다.
   
3. intArrOne[p1]< intArrTwo[p2]을 비교해서 더 작은 값(이 경우 intArrOne[p1])을 answer에 추가한다.
   
4. 그리고 p1을 추가했으니까 p1을 하나 값을 늘린다.
   

if(intArrOne[p1]< intArrTwo[p2]) {
    answer.add(intArrOne[p1]);
    p1++;
}
//이거랑 똑같은 코드
if(intArrOne[p1]< intArrTwo[p2]) answer.add(intArrOne[p1++]);

1. 그렇게 p1, p2를 다 비교하면 더 작은 배열이 먼저 끝나버린다.
   
2. 그러면 남아있는 배열을 answer에 추가해주어야 한다.
   
3. 이 때도 남아있는 p2를 하나씩 늘려가면서 추가한다.
   
4. 두 배열이 오름차순으로 정렬되어서 주어지기에 남은 배열은 그냥 뒤에다가 합쳐버려도 괜찮음.
   

🔵 ThingsILearned

✔️ System.arraycopy()

System.arraycopy(intArrOne, 0, answer, 0, n);
intArrOne을 0에서부터 복사해서 answer에 붙여넣는데, answer의 0부터 n까지 붙여넣으세요.

🟢 두 배열을 합친 후 오름차순으로 풀기

하지만 이 방법은 시간복잡도가 높기 때문에 추천하지 않는다.

class Main {

    public int[] solution(int n, int[] intArrOne, int m, int[] intArrTwo){
    int[] answer= new int[n+m];
    System.arraycopy(intArrOne, 0, answer, 0, n);
    //intArrOne을 복사하세요. 0인덱스에서 시작해서 answer로 복사하는데, 0에서 n까지
    System.arraycopy(intArrTwo, 0, answer, n, m);

    int temp=0;
    for(int i=0; i<n+m; i++){
        for(int j=i+1; j<n+m;j++) {
            if (answer[i] > answer[j]){
                temp= answer[i];
                answer[i]= answer[j];
                answer[j]= temp;
            }

        }
    }

    return answer;
}
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int[] intArrOne = new int[n];
        for(int i=0; i<n; i++){
            intArrOne[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] intArrTwo = new int[m];
        for(int j=0; j<m; j++){
            intArrTwo[j] = sc.nextInt();
        }
        for(int x: T.solution(n, intArrOne, m, intArrTwo)){
            System.out.print(x+ " ");
        }
    }
}