[java 백준] 실버 5/11728번 배열 합치기

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

11728번: 배열 합치기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
    public static int m;
    // 정렬배열은 반드시 전역변수로 선언
    public static int[] arr;
 
    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];
        int len = n + m;
        arr = new int[len];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
 
        }
        Arrays.sort(a);
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(st.nextToken());
 
        }
        Arrays.sort(b);
        StringBuilder sb = new StringBuilder();
 
        int i = 0;// a 배열 탐색해주는 포인터
        int j = 0;// b배열 탐색해주는 포인터
        int k = 0;// 정렬된 마지막 배열의 포인터
 
        while (i < n && j < m) {
            if (a[i] <= b[j]) {
                arr[k] = a[i];
                i++;
                k++;
            } else {
                arr[k] = b[j];
                j++;
                k++;
            }
        }
        if (i >= n) {
            //a 배열이 먼저 탐색 완료되면 정렬된 b 배열의 나머지 원소들을 arr에 넣어주기
            for (int t = j; t < m; t++) {
                arr[k] = b[t];
                k++;
            }
        } else {
            //b 배열이 먼저 탐색 완료되면 정렬된 a 배열의 나머지 원소들을 arr에 넣어주기
            for (int t = i; t < n; t++) {
                arr[k] = a[t];
                k++;
            }
        }
 
        for (int t = 0; t < k; t++) {
            sb.append(arr[t]).append(" ");
        }
        System.out.println(sb.toString());
 
    }
}

 

 

이 문제는 병합정렬을 이용해서 풀어주면 된다.

병합 정렬은 nlogn의 시간복잡도를 가지는데, 메모리를 많이 써서 그런지 채점속도가 제법 킹받았다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ndb796&logNo=221227934987 

7. 병합 정렬(Merge Sort)

 

위 글은 병합정렬을 소개한 글 인데 나도 이 글을 보며 병합 정렬을 이해했기에 첨부한다.