글 읽기 - 접미사 문제 시간복잡도

xgboost 5년 전 0

처음에 이문제를 O(N^2) 방법으로 for(int i=0; i<len; i++) for(int j=i;j<len; j++)
으로 접근해서 AC를 받았습니다. 근데 다른방법으로 누적합을 구하는 방법으로
뒤에서 부터 문자열을 더해주면서 계속 reverse를 해준후에 배열에 저장했습니다.
근데 채점결과 시간이 비슷하길래 좀 의아해서 질문남깁니다. reverse 함수때문에
o(n^2)과 비슷한건가요???

#include <iostream>
#include <algorithm>
#include <string>
#define MAX_SIZE 1000
using namespace std;

string prefix[MAX_SIZE + 1];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string s;
	string tmp;
	cin >> s;
	int len = s.size();
	string word = "";
	for (int i = len - 1; i >= 0; i--) {
		word += s[i];
		tmp = word;
		reverse(word.begin(), word.end());
		prefix[i] = word;
		word = tmp;
	}
	sort(prefix, prefix + len);
	for (int i = 0; i < len; i++) {
		cout << prefix[i] << '\n';
	}
}

djm03178 5년 전 1

이 문제는 필연적으로 O(N^2)일 수밖에 없습니다. 일단 출력해야 하는 문자 수부터 O(N^2)입니다.

말씀하신 대로 reverse 함수는 문자열 전체를 문자 하나씩 방문하며 위치를 바꿔야 하기 때문에 O(N) 시간이 걸리고, 이를 N번 수행하니 총 O(N^2)의 시간이 걸립니다. 또한 tmp = word나 prefix[i] = word, word = tmp 같은 것도 객체 안에 들어있는 모든 O(N)개의 문자들을 전부 하나씩 복사해야 하기 때문에 총 O(N^2)의 시간이 걸립니다.

xgboost 5년 전 0

친절한 설명감사합니다!!

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

문제

문제

출처

ICPC

접미사 문제 시간복잡도

xgboost 5년 전 0

djm03178 5년 전 1

xgboost 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말