[백준] 11728. 배열 합치기

문제 링크

[백준] 11728. 배열 합치기

풀이 과정

두 배열을 각각 가리키는 두 개의 포인터, 즉 투 포인터를 사용해서 배열을 하나의 배열로 만듭니다.

각 배열의 인덱스를 가리키는 두 개의 변수와, 합친 배열의 인덱스를 가리키는 변수, 총 세 개로 각각을 순회합니다. 포인터가 가리키는 위치의 요소끼리 크기 비교를 해, 더 작은 값을 결과 배열에 담아주고, 관련된 인덱스들을 증가시킵니다.

위의 또 다른 예제에서처럼, 한쪽 배열의 순회가 먼저 끝나버리는 경우, 다른 배열의 남은 요소들을 차례로 담아 주어야 합니다.

코드

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

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());
        int M = Integer.parseInt(st.nextToken());
        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());

        int idx_a = 0, idx_b = 0, idx = 0;
        int[] result = new int[N + M];

        while (idx_a < N && idx_b < M) {
            if (A[idx_a] >= B[idx_b]) result[idx++] = B[idx_b++];
            else if (A[idx_a] < B[idx_b]) result[idx++] = A[idx_a++];
        }

        while (idx_a < N)
            result[idx++] = A[idx_a++];

        while (idx_b < M)
            result[idx++] = B[idx_b++];

        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < N + M; i++) sb.append(result[i] + " ");

        System.out.println(sb);
    }
}