글 읽기 - 이문제 시간이 왜이렇게 짧게 걸리나요?

p_ce1052 3년 전 0

아래와 같은 코드를 사용하였는데 s가 100만개의 a이고 t가 100개의 b라고 하면 대충 비교 횟수가 9999만번이 되는데 어떻게 88ms안에 끝나나요? 그런 데이터가 없는건가요?

#include<bits/stdc++.h>
using namespace std;
int main(){
	string s,t;
	cin>>s>>t;
	int n = t.length();
	vector<char>st;
	for(int i=0; s[i]; i++){
		st.push_back(s[i]);
		if(st.size()<n) continue;
		bool same = true;
		for(int j=0; j<n; j++){
			if(t[n-1-j]!=st[st.size()-1-j]){
				same = false;
				break;
			}
		}		
		if(same) for(int i=0; i<n; i++) st.pop_back();
	}
	//if(st.empty()) cout<<"FRULA";
	for(int i=0; i<st.size(); i++) cout<<st[i];
}

djm03178 3년 전 1

요즘 컴퓨터라면 단순 연산은 1초에 10억~20억 정도 할 수 있으니 1억에 0.1초 걸리는 건 이상하지 않습니다.

p_ce1052 3년 전 0

지금까지 1억 = 1초로 생각하고 시간복잡도를 계산해왔는데 이제 이것도 다르게 생각해야 하려나요 djm님은 몇 번= 1초 로 계산하시나요?

djm03178 3년 전 1

저는 단순 연산을 1초 10억으로 보고 실제 연산이 얼마나 무거운지에 따라 적당히 배율을 조정하는 편입니다,

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

문제

문제

출처

ICPC

이문제 시간이 왜이렇게 짧게 걸리나요?

p_ce1052 3년 전 0

djm03178 3년 전 1

p_ce1052 3년 전 0

djm03178 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말