[머지 소트] 배열 합치기 (boj.kr/11728)

배열 합치기 (boj.kr/11728)

 

풀이코드 (시간 초과)

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
#include <string>
using namespace std;
// 11728 배열 합치기

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> a(n + 1);
	vector<int> b(m + 1);
	
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= m; i++) cin >> b[i];
	
	vector<int> ans;
	
	int idxA = 1 , idxB = 1;
	bool flagA = false, flagB = false;
	
	while(true){
		if(idxA > n){
			flagA = true;
			break;
		}
		else if(idxB > m){
			flagB = true;
			break;
		}
		
		if(a[idxA] > b[idxB]){
			ans.push_back(b[idxB]);
			idxB++;
		}
		else{
			ans.push_back(a[idxA]);
			idxA++;
		}
	}
	if(flagA){
		for(int i = idxB; i <= m; i++){
			ans.push_back(b[i]);
		}
	}
	else if(flagB){
		for(int i = idxA; i <= n; i++){
			ans.push_back(a[i]);
		}
	}
	
	for(int a : ans){
		printf("%d ", a);
	}
}

풀이코드 (시간 초과는 아니지만 매우 느림)

cin 을 scanf 로 바꾸었더니 시간 초과는 면함. 입출력 신경써야 한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
#include <string>
using namespace std;
// 11728 배열 합치기

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> a(n + 1);
	vector<int> b(m + 1);
	
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
	
	vector<int> ans;
	
	int idxA = 1 , idxB = 1;
	bool flagA = false, flagB = false;
	
	while(true){
		if(idxA > n){
			flagA = true;
			break;
		}
		else if(idxB > m){
			flagB = true;
			break;
		}
		
		if(a[idxA] > b[idxB]){
			ans.push_back(b[idxB]);
			idxB++;
		}
		else{
			ans.push_back(a[idxA]);
			idxA++;
		}
	}
	if(flagA){
		for(int i = idxB; i <= m; i++){
			ans.push_back(b[i]);
		}
	}
	else if(flagB){
		for(int i = idxA; i <= n; i++){
			ans.push_back(a[i]);
		}
	}
	
	for(int a : ans){
		printf("%d ", a);
	}
}

풀이코드 (vector 에 넣지 않고, 바로 출력하는 방식)

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
#include <string>
using namespace std;
// 11728 배열 합치기

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> a(n + 1);
	vector<int> b(m + 1);
	
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
	
	vector<int> ans;
	
	int idxA = 1 , idxB = 1;
	bool flagA = false, flagB = false;
	
	while(true){
		if(idxA > n){
			flagA = true;
			break;
		}
		else if(idxB > m){
			flagB = true;
			break;
		}
		
		if(a[idxA] > b[idxB]){
			printf("%d ", (b[idxB]));
			idxB++;
		}
		else{
			printf("%d ", (a[idxA]));
			idxA++;
		}
	}
	if(flagA){
		for(int i = idxB; i <= m; i++){
			printf("%d ", (b[i]));
		}
	}
	else if(flagB){
		for(int i = idxA; i <= n; i++){
			printf("%d ", (a[i]));
		}
	}
}

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. merge sort 의 기본이 되는 문제이다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 입력 받는 값들이 최대 1,000,000 개이다. 이런 문제에서는 무조건 입출력 방식을 신경써야 한다. 저수준 입출력 방식인 scanf pritnf 를 되도록이면, 사용하자.