[C++] 두 배열 합치기

📄문제

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

⬇️ 입력

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 배열의 원소는 int형 변수의 크기를 넘지 않습니다.

3 1 3 5 5 2 3 6 7 9

 

⬆️ 출력

오름차순으로 정렬된 배열을 출력합니다.

1 2 3 3 5 6 7 9

 

📝 풀이

#include <iostream>
#include <vector>

std::vector<int> vMergeAscending(std::vector<int> a, std::vector<int> b)
{
	std::vector<int> res(a.size() + b.size());

	int aIdx = 0, bIdx = 0;

	for (int i = 0; i < res.size(); ++i)
	{
		if (aIdx == a.size())
			for (int j = bIdx; j < b.size(); ++j)
				res[i++] = b[j];
		else if (bIdx == b.size())
			for (int j = aIdx; j < a.size(); ++j)
				res[i++] = a[j];
		else if (a[aIdx] == b[bIdx])
		{
			res[i] = a[aIdx++];
			res[++i] = b[bIdx++];
		}
		else
			res[i] = a[aIdx] < b[bIdx] ? a[aIdx++] : b[bIdx++];
	}

	return res;
}

int main()
{
	int N, M;
	scanf_s("%d", &N);
	std::vector<int> arrN(N);
	for (int i = 0; i < N; ++i)
		scanf_s("%d", &arrN[i]);

	scanf_s("%d", &M);
	std::vector<int> arrM(M);
	for (int i = 0; i < M; ++i)
		scanf_s("%d", &arrM[i]);

	std::vector<int> res = vMergeAscending(arrN, arrM);

	for (int i = 0; i < res.size(); ++i)
		printf("%d ", res[i]);
}

• 문제 조건에서 오름차순으로 정렬된 두개의 배열을 합치는 경우로, 함수를 작성하여 새로운 벡터 배열을 리턴하는 방식으로 문제를 해결하였습니다.
• 함수에 두개의 벡터를 넣으면 두개의 크기가 합쳐진 새로운 벡터를 생성합니다.
• 두개의 배열에 각 idx 번호를 비교하여 서로 같으면 idx를 각각 1씩 증가시키며 생성된 벡터에도 값을 추가합니다.
• 만약 둘 중 하나라도 idx 번호가 끝까지 도달했다면, 나머지 하나의 배열에서 모든 값을 생성된 벡터에 삽입합니다.