글 읽기 - 시간초과 관련해서

jerryprk 5년 전 0

채점을엄청느리게했습니다

string이 기본적으로 시간엄청잡아먹는데 원래는 시간초과 될법한 코드인가요?

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;

int testcase;
int t;
int A, B;
bool check[10000];
typedef struct data {
	int value;
	string order;
}Data;
string res;
int D(int a) {
	if(a*2 > 9999) return (a*2)%10000;
	else return a*2;
}
int S(int a) {
	if (a == 0) return a = 9999;
	else return a-1;
}
int L(int a) {
	int m = a/1000;
	a = (a % 1000) * 10 + m;
	return a;
}
int R(int a) {
	int m = (a % 10) * 1000;
	a = (a / 10) + m;
	return a;
}
void solve() {
	memset(check, 0, sizeof check);
	queue <Data> q;
	q.push({ A, });

	while (!q.empty()) {
		Data out = q.front(); q.pop();
		if (out.value == B) {
			res = out.order;
			break;
		}
		cout << out.order << "\t\t" << out.value << endl;
		Data in = { out.value, out.order};
		in.value = D(out.value);
		if (check[in.value] == false) {
			check[in.value] = true;
			in.order = out.order + "D";
			q.push(in);
		}in.value = S(out.value);
		if (check[in.value] == false) {
			check[in.value] = true;
			in.order = out.order + "S";
			q.push(in);
		}in.value = L(out.value);
		if (check[in.value] == false) {
			check[in.value] = true;
			in.order = out.order + "L";
			q.push(in);
		}in.value = R(out.value);
		if (check[in.value] == false) {
			check[in.value] = true;
			in.order = out.order + "R";
			q.push(in);
		}
	}
}
int main() {
#ifdef _CONSOLE
	freopen("sample.txt", "r", stdin);
#endif

	scanf("%d", &testcase);
	for (int i = 0; i < testcase; i++) {
		scanf("%d %d", &A, &B);
		solve();

		cout << res << endl;
	}
}

seico75 5년 전 0

in 을 만들때, in 에서 order 를 만들때, 그리고 push 할때 string 복사가 이루어질 것 같습니다.

이것을 아래와 같이 줄이면 4초대로 들어갈 수 있을 것 같고

        int v;
        v = D(out.value);
        if (check[v] == false) {
            check[v] = true;
            q.push( { v, out.order + "D");
        }

여기에서 정답(B) 이 나왔는지를 queue 에 넣기 전에 (위의 push 전정도)에 4번 넣으면 2초대..

string 복사를 빼면 1초미만이 나올 것 같습니다.

jerryprk 5년 전 0

아아 시간이 걸리는 이유가 string복사때문이고

그 문장자체들을 간략하거나 직접적으로 push해주는거군요! 감사합니다

시간을신경써본적이 없어서 무지한게 죄인것같네요

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

문제

문제

출처

ICPC

시간초과 관련해서

jerryprk 5년 전 0

seico75 5년 전 0

jerryprk 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말