글 읽기 - 두 코드의 시간복잡도 차이가 어디서 발생하는 건가요?

(追記) (追記ここまで)

두 코드의 시간복잡도 차이가 어디서 발생하는 건가요?

11478번 - 서로 다른 부분 문자열의 개수

kyb1208tg 1년 전 0

단순히 using namespcae std; 를 사용하고 안하고의 차이인거 같은데 왜 2번코드에서는 시간초과가 나오는지 모르겠습니다

//1. 정답코드
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
	std::string str;
	std::cin >> str;
	int count = 0;
	for (int i = 0; i < str.size(); i++)
	{
		std::vector<std::string> v;
		for (int j = 0; j < str.size() - i; j++)
		{
			std::string tmp = str.substr(j, 1 + i);
			v.push_back(tmp);
		}
		
		std::sort(v.begin(), v.end());
		v.erase(std::unique(v.begin(), v.end()), v.end());
		count += v.size();
	}
	std::cout << count;
}
//2. 시간초과
#include<cstring>
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#define MAX_SIZE 10001
#define FIO cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
int main(){
 FIO;
 string str;
 cin>>str;
 vector<string> s;
 int len = str.length();
 for(int i=0;i<len;i++){ //길이
 for(int j=0;j<len-i;j++){ //시작 범위
 string tmp = str.substr(j, i+1);
// cout<<tmp<<"\n";
 s.push_back(tmp);
 }
 }
 sort(s.begin(), s.end());
 s.erase(unique(s.begin(), s.end()), s.end());
 int count = 0;
 count += s.size();
 cout<<count<<"\n";
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

두 코드의 시간복잡도 차이가 어디서 발생하는 건가요?

kyb1208tg 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말