문제

BOJ 11728, 배열합치기

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 최대 100만개의 크기를 가진 배열 a, b를 효율적으로 합쳐야 하므로 병합정렬의 핵심 아이디어인 두 배열의 요소를 하나씩 비교해서 작은 값을 먼저 출력한다.

개선

코드

시간복잡도

• $O(N \times log_2N)$

C++

#include <iostream>
using namespace std;

int a[1'000'004];
int b[1'000'004];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> a[i];
	for (int i = 0; i < m; ++i) cin >> b[i];
	int l = 0;
	int r = 0;
	for (int i = 0; i < n + m; ++i) {
		if (l == n)
			cout << b[r++] << ' ';
		else if (r == m)
			cout << a[l++] << ' ';
		else if (a[l] > b[r])
			cout << b[r++] << ' ';
		else
			cout << a[l++] << ' ';
	}
}

Java

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

public class J11728_배열합치기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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 l = 0, r = 0;
        for (int i = 0; i < n + m; ++i) {
            if (l == n)
                bw.write(b[r++] + " ");
            else if (r == m)
                bw.write(a[l++] + " ");
            else if (a[l] < b[r])
                bw.write(a[l++] + " ");
            else
                bw.write(b[r++] + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

• 아래서부터 C++ 고정 배열, Java ArrayList, Java 고정 배열 사용한 결과다. C++에서는 내가 메모리를 얼마나 사용하는지 예상할 수 있다. 200만개의 int형 배열을 선언했으니 대략 8000KB이고 나머지는 프로그램 실행을 위한 메모리 사용량으로 볼 수 있다. 하지만 Java에서는 가비지 컬렉션, 입출력을 위한 객체, 클래스 정보 등으로 정확한 메모리 사용량을 예측하기 어렵다.