[백준][C++] 11728: 배열 합치기

문제 링크: https://www.acmicpc.net/problem/11728

 

입력되는 배열이 정렬된 채로 입력된다는 점에서 선형 시간에 문제를 해결해봅시다.

 

n+1, m+1짜리 배열을 만들고 배열을 전체 쭉 넣은 뒤 맨 뒷칸에 모든 배열값보다 큰 값을 넣습니다. 왜냐면 투포인터로 배열을 합칠건데 편의를 위해 그렇습니다.

그 다음 각 배열의 인덱스 두개(i1, i2)를 만들어줍니다. 두개 비교해서 두개가 같으면 둘다 한 칸씩 뒤로 이동하고 두 개 출력, 한 쪽이 작으면 작은 쪽을 출력하고 작은쪽 인덱스를 뒤로 한칸 이동합니다. i1, i2 둘다 맨 뒤로 이동(n, m)할 때까지 반복하면 됩니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector<int> v1(n), v2(m);
	for (auto& c : v1)
		cin >> c;

	for (auto& c : v2)
		cin >> c;

	v1.push_back(1e9 + 1);
	v2.push_back(1e9 + 1);

	int i1 = 0, i2 = 0;
	while (i1 < n || i2 < m) {
		if (i1 != 0 || i2 != 0) cout << ' ';
		
		if (v1[i1] == v2[i2]) {
			cout << v1[i1] << ' ' << v1[i1];
			++i1, ++i2;
		}
		else if (v1[i1] < v2[i2]) {
			cout << v1[i1];
			++i1;
		}
		else {
			cout << v2[i2];
			++i2;
		}
	}

	return 0;
}

 

 

배열을 입력받아서 그냥 std::sort로 정렬하면 시간초과가 나올 줄 알았는데 아니네요

수행시간도 뭐 거의 비슷합니다.