문제

백준 11728번
https://www.acmicpc.net/problem/11728

정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)
둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.

첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.

Code

• 초기 상태
  

• A[p1]과 B[p2] 비교(p1 = 0, p2 = 0)
  

• A[p1]과 B[p2] 비교(p1 = 0, p2 = 1)
  

• A[p1]과 B[p2] 비교(p1 = 1, p2 = 1)
  

• p1이 A.length와 같이 때문에 while(p1 == A.length && p2 != B.length) 실행(p1 = 2, p2 = 1)
  

• p1과 p2 둘 다 A, B 배열의 길이와 같기 때문에 while문 종료 후 결과 반환

  • [2 3 5 9]

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());  // 배열 A의 크기
        int M = Integer.parseInt(st.nextToken());  // 배열 B의 크기
        int[] A = new int[N];
        int[] B = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        int p1 = 0;  // A 배열의 인덱스
        int p2 = 0;  // B 배열의 인덱스
        while (true) {
            // B배열 값들은 모두 추가 후 A배열의 남은 값들을 추가
            while (p1 != A.length && p2 == B.length) {
                sb.append(A[p1++]).append(" ");
            }

            // A배열 값들은 모두 추가 후 B배열의 남은 값들을 추가
            while (p1 == A.length && p2 != B.length) {
                sb.append(B[p2++]).append(" ");
            }

            // A 배열과 B 배열 값들을 모두 추가했을 경우
            if (p1 == A.length && p2 == B.length) {
                break;
            }

            // A[p1]보다 B[p2] 더 큰 경우
            if (A[p1] < B[p2]) {
                sb.append(A[p1++]).append(" ");
            } else {
                sb.append(B[p2++]).append(" ");
            }
        }
        System.out.println(sb);
    }
}