알고리즘 문제풀기/인프런 강의 정답
39. 두 배열 합치기(병합정렬 예비학습) [정렬 & 이분탐색(결정알고리즘) & 투포인트 알고리즘 & 스택]
코다람쥐
2022. 4. 11. 10:48
나의정답
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main(int argc, char** argv) {
freopen("input.txt", "rt", stdin);
int n, m, i, j, idx, tmp;
// a배열 초기화
scanf("%d", &n);
vector<int> a(n);
for(int i = 0 ; i < n; i++)
scanf("%d", &a[i]);
// b배열 초기화
scanf("%d", &m);
vector<int> b(m);
for(int i = 0 ; i < m; i++)
scanf("%d", &b[i]);
// c배열 = a배열 + b배열
vector<int> c(n + m);
for(int i = 0; i < n; i++){
c[i] = a[i];
}
for(int i = n; i < n + m; i++){
c[i] = b[i - n];
}
// 삽입정렬
for(i = 1 ; i < n + m - 1; i++){
tmp = c[i];
for(j = i - 1; j >= 0; j--){
if( c[j] > tmp )
c[j+1] = c[j];
else
break;
}
c[j+1] = tmp;
}
/* 버블정렬
for(i = 0; i < n + m; i++){
for(j = 0 ; j < n + m - i - 1; j++){
if(c[j] > c[j+1]){
tmp = c[j];
c[j] = c[j+1];
c[j+1]= tmp;
}
}
}*/
/* 선택정렬
for(i = 0; i < n + m - 1; i++){
idx = i;
for(j = i + 1; j < n + m ; j++){
if(c[idx] > c[j]) idx = j;
}
tmp = c[i];
c[i] = c[idx];
c[idx] = tmp;
}*/
for(int i = 0; i < n + m; i++)
printf("%d ", c[i]);
}