글 읽기 - C++ 시간 초과 이유를 모르겠습니다.

lisagamer 2년 전 0

두 배열의 인덱스를 활용하였고, O(n+m)으로 해결되는 것 같은데 시간초과가 납니다. 반복문에서 무한루프를 돌게 되는 경우가 있는 것 같기도 한데 어떤 문제가 있을까요?

#include <iostream>
#include <algorithm>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>

using namespace std;

int N, M;

int main()
{
	cin >> N >> M;
	vector<int> A(N);
	vector<int> B(M);
	vector<int> result(N + M);
	for (int i = 0; i < N; i++)
		cin >> A[i];
	for (int j = 0; j < M; j++)
		cin >> B[j];

	// O(n+m)에 가능
	int idx = 0;
	int ptrA = 0;
	int ptrB = 0;
	// 종료 조건 -> 한쪽의 입력이 모두 끝날 경우
	while (ptrA != N && ptrB != M)
	{
		// 대소비교
		// 작은 놈을 넣기
		if (A[ptrA] > B[ptrB])
			result[idx++] = B[ptrB++];
		else
			result[idx++] = A[ptrA++];
	}
	// 남은 놈 밀어넣기
	// A가 남았을 때 
	if (ptrA != N)
	{
		while (ptrA != N)
			result[idx++] = A[ptrA++];
	}
	else
	{
		while (ptrB != M)
			result[idx++] = B[ptrB++];
	}

	for (auto num : result)
		cout << num << ' ';
	
}
 

palilo 2년 전 1

15552번: 빠른 A+B (acmicpc.net)

이거 먼저 풀어보세요

lisagamer 2년 전 0

아 이것 때문에 시간초과 날거라고는 생각을 못 했네요.. 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++ 시간 초과 이유를 모르겠습니다.

lisagamer 2년 전 0

palilo 2년 전 1

lisagamer 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말