BOJ 11728 (배열 합치기)

• 문제
  정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.
  
  
• 입력
  첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)
  
  둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.
  
  
• 출력
  첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
int firstArr[1000001];
int secondArr[1000001];
vector<int> answerVector;
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void input()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		cin >> firstArr[i];
		answerVector.push_back(firstArr[i]);
	}
	for (int i = 0; i < M; i++)
	{
		cin >> secondArr[i];
		answerVector.push_back(secondArr[i]);
	}
}

int main()
{
	fast_io();
	input();
	sort(answerVector.begin(), answerVector.end());
	for (int i = 0; i < answerVector.size(); i++)
	{
		cout << answerVector[i] << ' ';
	}
	return 0;
}

   두 배열의 입력을 각각 받고 하나의 배열에 합쳐서 정렬을 해주면 끝나는 문제이다. 1.5초의 시간제한에 배열의 길이가 100만 까지라 O(N^2)이상이면 시간초과가 날 것이라 판단했다.

시간복잡도 : O(NlogN)

다른 풀이를 참고하려했는데 문제가 바뀐 것 같다 (기존 : 정렬이 되어있는 배열 합치기)
-> Merge Sort 이용
(각 배열의 시작 index부터 합치려는 두 배열의 각 위치에서 값 비교 후 결과를 출력할 배열에 작은 것부터 넣어주면 된다)

숏코딩 -> 하나의 벡터에 넣어 풀이

#include<bits/stdc++.h>
using namespace std;
int main()
{ vector<int>v;
  int N,M;scanf("%d%d",&M,&N);
  v.resize(N+M);
  for(int i=0;i<N+M;i++)	
  {scanf("%d",&v[i]);}
  sort(v.begin(),v.end());
  for(auto&ele:v){cout<<ele<<" ";}
  return 0;
  }