[백준] 11728번 : 배열 합치기 (JAVA)

🔗 문제 링크

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

---

📌 문제 개요

정렬된 두 배열 A와 B가 주어질 때, 두 배열을 합쳐 정렬된 상태로 출력하는 문제

A = 1 4 7  
B = 2 3 6

 

이라면 결과는 1 2 3 4 6 7 처럼 두 배열을 합친 후 정렬된 상태로 출력해야 한다.

---

📌 접근 방법

처음에는 두 배열을 하나의 배열로 합친 후 Arrays.sort()로 정렬하는 방법도 생각할 수 있다.

하지만 이 문제는 이미 두 배열이 각각 정렬된 상태이기 때문에
다시 정렬할 필요 없이 Merge 방식으로 해결할 수 있다.

 

Merge 방식은 두 포인터를 사용하여 두 배열의 현재 값을 비교하면서 작은 값을 순서대로 결과에 넣는 방법

---

📌 핵심 아이디어

1. 배열 A와 B를 각각 입력받는다.
2. 두 배열의 현재 위치를 가리키는 포인터 i, j를 만든다.
3. A[i]와 B[j]를 비교하여 작은 값을 결과에 추가한다.
4. 해당 포인터를 증가시킨다.
5. 한 배열이 끝나면 다른 배열의 남은 요소들을 모두 추가한다.
6. 결과는 StringBuilder에 저장한 뒤 한번에 출력한다.

시간복잡도는 O(A + B) 이다.

---

📌 전체 코드

package no_11728;

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

public class No11728 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] A = new int[Integer.parseInt(st.nextToken())];
        int[] B = new int[Integer.parseInt(st.nextToken())];

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

        for(int i = 0; i < A.length; i++){
            A[i] = Integer.parseInt(st1.nextToken());
        }

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

        for(int j = 0; j < B.length; j++){
            B[j] = Integer.parseInt(st2.nextToken());
        }

        StringBuilder sb = new StringBuilder();

        int i = 0;
        int j = 0;

        while(i < A.length && j < B.length){
            if(A[i] <= B[j]){
                sb.append(A[i++]).append(" ");
            }else{
                sb.append(B[j++]).append(" ");
            }
        }

        while(i < A.length){
            sb.append(A[i++]).append(" ");
        }

        while(j < B.length){
            sb.append(B[j++]).append(" ");
        }

        System.out.print(sb);
    }
}

---

📌 정리

이 문제의 핵심은 이미 정렬된 배열을 다시 정렬하지 않는 것이다.

Arrays.sort()를 사용하면 O(N log N)이 되지만,

 

Merge 방식(투포인터)을 사용하면 O(N) 으로 해결할 수 있다.