[투포인터] 두 배열 합치기

설명

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

입력

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

코드 및 문제해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int[] nArray;
    static int[] mArray;
    static ArrayList<Integer> result = new ArrayList<>();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        nArray = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            nArray[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        mArray = new int[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            mArray[i] = Integer.parseInt(st.nextToken());
        }

        solution(0, 0, N, M);

        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i) + " ");
        }

    }

    public static void solution(int start, int end, int N, int M) {
        //배열끼리 포인트로 비교하여 오름차순 정렬한다.
        while (start < N && end < M) {
            if (nArray[start] < mArray[end]) {
                result.add(nArray[start]);
                start++;
            } else if (nArray[start] > mArray[end]) {
                result.add(mArray[end]);
                end++;
            } else {
                result.add(nArray[start]);
                result.add(mArray[end]);
                start++;
                end++;
            }
        }

        //정렬 후 M이 먼저 끝났을 경우 나머지 값을 배열에 삽입
        while (start < N) {
            result.add(nArray[start]);
            start++;
        }
        //정렬 후 N이 먼저 끝났을 경우 나머지 값을 배열에 삽입
        while (end < M) {
            result.add(mArray[end]);
            end++;
        }
    }
}

• 투포인트에서 P1,P2 를 어떻게 설정해야할지 정해야한다.
• 여기서는 두 배열이니 각 배열의 첫 인덱스를 P1, P2 로 각각 설정한다.
• P1 과 P2 를 대소비교하며 포인터를 증가시키면서 끝위치까지 도달하면 로직을 멈추면 된다.

result.add(mArray[end]);
end++;

----- 후위 증감연산자를 쓰면 코드가 깔끔해질듯

result.add(mArray[end++]);

if (nArray[start] < mArray[end]) {
      result.add(nArray[start]);
      start++;
} else if (nArray[start] > mArray[end]) {
    result.add(mArray[end]);
    end++;
} else {
    result.add(nArray[start]);
    result.add(mArray[end]);
    start++;
    end++;
}

-------- 아래와 같이 변경해도 상관없다.

if (nArray[start] < mArray[end]) {
    result.add(nArray[start]);
    start++;
} else {
    result.add(mArray[end]);
    end++;
} 

같은 수는 비교안해도 다음 비교 때 큰 수와 비교 되므로 굳이 비교문을 넣을 필요가 없다.

1 3 5 
2 3 6 7 9 

주어진 예제를 진행해보면 아래와 같이 포인트 위치하게된다.

1 2 3(P2) 

여기서 P1, P2 가 같은 수면 else 절이 실행되므로 P2(3)이 오름차순 배열에 추가되고 
P2는 6이 된다.
그러면 P1의 3이 다음 비교때 정렬되므로 같은 수 비교는 굳이 할 필요가 없다.  

1 2 3(P2) 3(P1)