알고리즘 문제풀기/인프런 강의 정답

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]);
}