[Baekjoon] 11728번: 배열 합치기

https://www.acmicpc.net/problem/11728

11728번: 배열 합치기

문제 설명

정렬된 두 배열이 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하면 된다.

풀이 방법

투 포인터 기초 문제이다. 예제 입력 3을 그림을 통해 보자. 이해를 돕기 위해 A 배열에 10을 추가했다.

• A: 첫 번째로 주어진 배열이다.
• B: 두 번째로 주어진 배열이다.
• ans: 출력할 정답을 저장해놓는 배열이다. 첫째 줄에 입력받은 N과 M을 더한 길이로 만들었다.
• pA: A에서 현재 인덱스를 가리키는 포인터 변수이다.
• pB: B에서 현재 인덱스를 가리키는 포인터 변수이다.
• pAns: ans에서 현재 인덱스를 가리키는 포인터 변수이다.

 

이제 A와 B의 첫 번째 원소부터 비교해나간다.

1회전

1이 더 작으므로 ans[0]에 1을 저장하고 pAns와 pB를 1씩 증가시킨다.

2회전

2가 더 작으므로 ans[1]에 2를 저장하고 pAns와 pA를 1씩 증가시킨다.

이런 식으로 반복하면서 5회전까지 진행한다. 그러면 현재 상황은 다음과 같을 것이다.

5회전 진행 후

이제 6회전을 진행한다.

6회전

7이 더 작으므로 ans[5]에 7을 넣고 pAns와 pB를 증가시킨다. 그런데 이때 pB가 B의 배열 범위를 초과했다. 이 말은 B에는 더 비교할 원소가 없다는 뜻이다. 따라서 A의 나머지 원소들을 ans 배열의 뒤에 복사하기만 하면 된다. 이미 정렬된 배열로 주어지기 때문에 가능하다.

따라서 pA부터 A의 마지막 인덱스까지 ans의 pAns에 복사하기만 하면 된다.

복사 후

코드는 다음과 같다.

import java.io.*;
import java.util.Arrays;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] split = br.readLine().split(" ");
         
        int N = Integer.parseInt(split[0]);
        int M = Integer.parseInt(split[1]);
        
        int[] ans = new int[N + M];
        
        int[] A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] B = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        
        int pA = 0;
        int pB = 0;
        int pAns = 0;
        
        while (pA < N && pB < M) {
            if (A[pA] < B[pB]) {
                ans[pAns++] = A[pA++];
            } else {
                ans[pAns++] = B[pB++];
            }
        }
        
        if (pA == N) {
            System.arraycopy(B, pB, ans, pAns, M - pB);
        } else {
            System.arraycopy(A, pA, ans, pAns, N - pA);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            sb.append(ans[i]).append(" ");
        }
        System.out.print(sb);
    }
}