두 배열 합치기

설명

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

 

입력

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

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

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

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

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

 

출력

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

 

예시 입력 1 

3

1 3 5

5

2 3 6 7 9

 

예시 출력 1

1 2 3 3 5 6 7 9

 

 

** 일반적으로 이러한 문제를 풀때 이중for문을 사용하는 방법을 맨 처음 떠올리겠지만,

사실 기업에서 원하는 것은 O(n^2)의 복잡도를 O(n)으로 구현하는걸 할수 있는지를 궁금해 하는 거라고 한다.

되도록이면 O(n)이 되게 구현을 하자 ! **

 

<제출>

public static ArrayList<Integer> solution(int n, int m, int[] a, int[] b){
        ArrayList<Integer> answer = new ArrayList<>();

        int p1 =0, p2=0;

        while(p1<n && p2<m){
            if(a[p1] < b[p2]) answer.add(a[p1++]);
            else answer.add(b[p2++]);
        }
        
        while(p1<n) answer.add(a[p1++]);
        while(p2<m) answer.add(b[p2++]);

        return answer;
    }

 

- 설명

n이후의 값들을 순서대로 배열에 저장하는 이유는, 이미 배열a와 b가 오름차순 정렬이 되어있는 상태이기 때문이다.

(n이후의 값들은 모두 n보다 크다)

또한, p1과 p2 요소의 비교 이후에 다시 while문 두개를 사용해서 나머지 배열의 요소를 arr에 삽입하는 이유는, a와 b중에서 어떤 배열의 길이가 더 길지는 모르기 때문에 a와 b배열 중, n이후의 값들을 삽입해주는 것이다.