[백준 알고리즘] 11728번: 배열합치기
April 08, 2021
https://www.acmicpc.net/problem/11728
문제
문제
정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)
둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.
출력
첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.
풀이
투 포인터 알고리즘을 사용해서 풀었지만, 사실 머지소트의 동작과 비슷하다. 먼저 어느한쪽이라도 끝에 도달할 때 까지 두 배열에서 더 작은 숫자를 차례대로 꺼내서 새로운 배열에 넣고, 나머지 배열은 정렬시켜 순서대로 뒤에 넣어주는 방식으로 해결할 수 있다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
cin >> N >> M;
int A[N];
int B[M];
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int i = 0; i < M; i++) {
cin >> B[i];
}
int startA = 0, startB = 0;
int sum[N + M];
int sumIdx = 0;
sort(A, A+N);
sort(B, B+M);
while (startA != N && startB != M) {
if (A[startA] < B[startB]) {
sum[sumIdx++] = A[startA++];
}
else {
sum[sumIdx++] = B[startB++];
}
}
while (startA != N) {
sum[sumIdx++] = A[startA++];
}
while (startB != M) {
sum[sumIdx++] = B[startB++];
}
for (int i = 0; i < N + M; i++) {
cout << sum[i] << " ";
}
}
