공부 기록

C++ 백준 11728번

by 너나나

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

 

11728번: 배열 합치기

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

www.acmicpc.net

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

 

그냥 일반적인 정렬 방식을 쓰면 O(N^2) 시간이 걸리는데 여기서 배열의 최대 크기가 100만이므로 시간이 너무 오래 걸린다.

배열 A, B가 정렬되어있기 때문에 머지 소트를 이용해서 풀면 빠르게 풀수있다.(merge sort의 시간 복잡도는 O(nlogn)이고 여기서 미리 두 배열이 정렬되어있기때문에 합치는 과정만 하면 된다!!)

 

merge sort : n개를 정렬하는 알고리즘

n을 2/n, 2/n개로 나눠서 오른쪽 n/2와 왼쪽 n/2을 정렬하고 두 정렬한 결과를 하나로 합치면서 정렬하는 방법이다.

c++로 구현할 때 ios::sync_with_stdio(false), cin.tie(nullptr) 안 쓰면 시간 초과가 나온다. 저 두줄을 쓰거나 pritnf와 scanf로 구현해도 된다!

 

#include<iostream>
using namespace std;
int a[1000001];
int b[1000001];
int c[2000002]; // 합친 배열
int main() {
	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 i = 0; // a 배열의 index
	int j = 0; // b 배열의 index
	int k = 0; // c 배열의 index
	while (i < n && j < m) {
		if (a[i] < b[j]) {
			c[k++] = a[i++];
		}
		else c[k++] = b[j++];
	}
	while (i < n) {
		c[k++] = a[i++];
	}
	while (j < m) {
		c[k++] = b[j++];
	}
	for (int l = 0; l < n + m; l++) {
		cout << c[l] << ' ';
	}
	cout << '\n';
}
블로그의 프로필 사진

블로그의 정보

공부 기록

너나나

활동하기