Contents
문제
문제를 보시려면 링크를 클릭해주세요.
풀이
merge sort를 이용해 풀 수 있습니다.
이미 정렬되어 있는 두 배열의 최솟값을 비교하여,
더 작은 최솟값을 출력하는 방식으로 작성하였습니다.
(두 배열 크기합 - 1) 만큼 비교하면 되기에, 반복문 조건은 그에 맞춰 생성하였습니다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, M;
int A[1000001], B[1000001];
int chk1=0, chk2=0;
cin >> N >> M;
for(int i=0; i<N; i++)
cin >> A[i];
for(int i=0; i<M; i++)
cin >> B[i];
while (chk1 + chk2 < N + M){
if(chk1==N)
cout << B[chk2++] << " ";
else if(chk2==M)
cout << A[chk1++] << " ";
else{
if(A[chk1]>B[chk2])
cout << B[chk2++] << " ";
else
cout << A[chk1++] << " ";
}
}
return 0;
}