글 읽기 - 시간 초과 오류 ㅠㅠ

his130 7년 전 1

처음에 벡터로 해서 했는데 시간초과가 뜨더라구요

그래서 벡터로 이루어진 부분은 모두 주석처리해서

배열로 바꿔서 했는데 시간초과가 뜨네요 ㅠㅠㅠ

이중포문이 들어가는 부분도 없는데 ㅠㅠ

while문에서 시간복잡도가 커지는 건가요??..

어떻게 고쳐야되나요 ㅠㅠ

#include<iostream>
#include<vector>

using namespace std;

int N_num;
int M_num;
int R_num;
//vector<long long> N;
//vector<long long> M;
//vector<long long>R;;
int N[1000001];
int M[1000001];
long long R[2000001];

//void compare(vector<long long> N2, vector<long long> M2)
void compare()
{
	int i = 0;
	int j = 0;
	int k = 0;
	while (i < N_num && j < M_num)
	{
		if (N[i] >= M[j])
		{
			//R.push_back(M[j++]);
			R[k++] = M[j++];
		}
		else if (N[i] < M[j])
		{
			//R.push_back(N[i++]);
			R[k++] = N[i++];
		}
	
	}
	while (i < N_num)
	{
		//R.push_back(N[i++]);
		R[k++] = N[i++];
	}
	while (j < M_num)
	{
		//R.push_back(M[j++]);
		R[k++] = M[j++];
	}

	
	for (int q = 0; q < N_num + M_num; q++)
	{
		cout << R[q] << " ";
	}
	cout << endl;
}
int main()
{
	cin >> N_num >> M_num;

	for (int i = 0; i < N_num; i++)
	{
		int a;
		cin >> a;
		N[i] = a;
		//N.push_back(a);
	}

	for (int j = 0; j < M_num; j++)
	{
		int b;
		cin >> b;
		M[j] = b;
		//M.push_back(b);
	}
	compare();
	return 0;
}

yukariko 7년 전 1

cin cout대신 scanf printf를 사용해보세요

indioindio 7년 전 1

cin이 사실 엄청 빠른 편은 아닙니다.

std::ios_base::sync_with_stdio(false); 추가하시면 제 시간안에 들어오네요 (확인 차 제출해본 점 양해 부탁드립니다.) 자세한 건 아래 링크를 참조하시면 될 것 같아요.

저것만 추가하면 1036ms에 완료되는 데(원래 제한은 1초였죠),

그 외에도 cin >> b; M[j] = b; 를 cin >> M[j]로 고치기 (이 부분은 컴파일러가 최적화를 해줄 지 안 해줄지 잘 모르겠네요 아마 해줄 것 같긴 합니다)

R 배열에 넣은 다음 R의 원소들을 출력하는 대신 R배열에 넣지말고 바로바로 출력하기 등을 이용하시면 800ms 정도 걸리네요.

https://www.quora.com/Is-cin-cout-slower-than-scan...

his130 7년 전 0

아 cin cout 문제였군요

감사합니다!

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

문제

문제

출처

ICPC

시간 초과 오류 ㅠㅠ

his130 7년 전 1

yukariko 7년 전 1

indioindio 7년 전 1

his130 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말