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';
}
블로그의 정보
공부 기록
너나나