[Two pointers] 두 배열 합치기

 

 

 

설명

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

 

 

 

입력

첫 번째 줄에 첫 번째 배열의 크기 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

 

 

 

 

풀이

퀵 정렬을 하게 된다면 시간 복잡도는 O(N * log N) 이다.
60000 개의 데이터를 정렬한다고 하면, 60000 * 16 = 960000번 정렬해야 한다.

시간복잡도를 최소화 하기 위해서, O(N) 이 되도록 짜야 한다.

P1 이라는 포인터는 a 배열의 0번 인덱스를 가리킨다.
P2 이라는 포인터는 b 배열의 0번 인덱스를 가리킨다.

a[p1] < b[p2] 이면 answer(배열)에 a[p1]을 추가하고, p1 포인터를 1 증가시킨다.
그렇지 않다면 answer(배열)에 b[p2]를 추가하고, p2 포인터를 1 증가시킨다.
a[p1++], b[p2++]와 같이 후위 연산자를 사용한다.

하나의 배열의 포인터가 끝까지 왔다면 while문은 멈춘다. 

 

남은 배열은 끝까지 answer 에 넣는다.

 

 

 

 

 

코드

package inflearn._3_1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    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++]); // p1 이 가르키는 값을 add 하고 p1이 1 증가
            else answer.add(b[p2++]);
        }

        // a 배열이 남아있는 경우
        while(p1 < n) answer.add(a[p1++]);

        // b 배열이 남아있는 경우
        while(p2 < m) answer.add(b[p2++]);


        return answer;

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();



        int n = Integer.parseInt(br.readLine());
        int [] a = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        int [] b = new int[m];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(st.nextToken());
        }

        ArrayList<Integer> answer = solution(n, m, a, b);

        for(int i : answer) {
            sb.append(i).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();

        bw.close();
        br.close();

    }
}