[인프런] 두 배열 합치기

난이도

• Easy

문제 설명

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.
첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.

입력 형식

• 정수, 정수배열

출력 형식

• 정수 배열

예제 입력 및 출력

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

출력: 1 2 3 3 5 6 7 9

접근 방법

• 투 포인터를 사용한다
• 첫 번째 배열과 두 번째 배열, 첫 번째 배열의 index, 두 번째 배열의 index , 결과 배열의 index 선언
• 첫 번째 배열의 값과 두 번째 배열의 값을 비교해서 값이 작은 것들 결과 배열에 추가
• 이 때 결과 배열에 해당하는 인덱스 + 1 추가 및 결과 인덱스 + 1
• 배열에서 값을 추가하더라도 어떤 배열에 값이 남을 수 있으므로, 나머지 부분을 결과 배열에 추가

시간 및 공간 복잡도

• 시간 복잡도: O(n + m) - 첫 번째 배열 순회(m) + 두 번째 배열 순회(n)
• 공간 복잡도 : O(n) - 결과 배열 선언

코드 구현

import java.util.*;

public class App {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] array1 = new int[n];
        for (int i = 0; i < array1.length; i++) {
            array1[i] = sc.nextInt();
        }

        int k = sc.nextInt();
        int[] array2 = new int[k];
        for (int i = 0; i < array2.length; i++) {
            array2[i] = sc.nextInt();
        }

        int[] answer = new int[n + k];

        int array1Index = 0;
        int array2Index = 0;
        int answerIndex = 0;
        while (array1Index < n && array2Index < k) {
            if (array1[array1Index] > array2[array2Index]) {
                answer[answerIndex] = array2[array2Index];
                answerIndex++;
                array2Index++;
            } else {
                answer[answerIndex] = array1[array1Index];
                answerIndex++;
                array1Index++;
            }
        }
        while (array1Index < n) {
            answer[answerIndex] = array1[array1Index];
            answerIndex++;
            array1Index++;
        }

        while (array2Index < k) {
            answer[answerIndex] = array2[array2Index];
            answerIndex++;
            array2Index++;
        }

        for(int i : answer){
            System.out.print(i + " ");
        }
    }
}