[알고리즘][C++] 두 배열 합치기(병합정렬 예비학습)

a

🔽

1

3

5

 

b

🔽

2

3

6

7

9

 

c

🔽

1

 

---

a

                🔽

1

3

5

 

b

🔽

2

3

6

7

9

 

c

                🔽

1

2

 

---

 

a

                 🔽

1

3

5

 

b

               🔽

2

3

6

7

9

 

c

                               🔽

1

2

3

 

---

a

                🔽

1

3

5

 

b

                             🔽

2

3

6

7

9

 

c

                                                      🔽

1

2

3

3

 

 

 

---

a

                                 🔽

1

3

5

 

b

                             🔽

2

3

6

7

9

 

c

                                                                       🔽

1

2

3

3

5

 

한쪽 배열이 끝나면 break + 더 긴 배열의 나머지 값 삽입 

 

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int a[101], b[101], c[300];
int main(){ 
	//freopen("input.txt", "rt", stdin);
	int n, m, i, p1=1, p2=1, p3=1;
	
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
	}
	
	scanf("%d", &m);
	for(i=1; i<=m; i++){
		scanf("%d", &b[i]);
	}

	while(p1<=n && p2<=m){
		if(a[p1] < b[p2]) { //더 작은 값은 c 배열에 먼저 삽입 
			c[p3++]=a[p1++]; //배열에 대입 후에 증가(후위연산) 
		}
		else{
			c[p3++]=b[p2++];
		}
	}
    
    //더 긴 배열에 담긴 값 삽입하기
	while(p1<=n) c[p3++]=a[p1++];
	while(p2<=m) c[p3++]=b[p2++];

	for(i=1; i<=n+m; i++){
		printf("%d ", c[i]);
	}
	return 0;
}