글 읽기 - 고수님들 두 코드의 차이점을 알려주세요

dsa2341 4년 전 0

책과 블로그를 찾아보면서 문제를 해결해보려했는데 위와 아래의 코드가 무슨 차이로 시간 차이가 발생하는지 모르겠습니다

//시간초과가 난 코드


#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Comparator {
	const vector<int> group;
	int t;
	Comparator(const vector<int> _group, int _t) : group(_group), t(_t){}
	bool operator() (int a, int b) {
		if (group[a] != group[b]) return group[a] < group[b];
		return group[a + t] < group[b + t];
	}
};
vector<int> getSA(const string& s) {
	int n = s.size(), t = 1;
	vector<int>perm(n);
	vector<int>group(n + 1);
	for (int i = 0; i < n; ++i) {
		perm[i] = i;
		group[i] = s[i];
	}
	group[n] = -1;
	while (t < n) {
		Comparator compare(group, t);
		sort(perm.begin(), perm.end(), compare);
		t *= 2;
		if (t >= n) break;
		vector<int> newGroup(n + 1);
		newGroup[n] = -1;
		newGroup[perm[0]] = 0;
		for (int i = 1; i < n; ++i)
			if (compare(perm[i - 1], perm[i]))
				newGroup[perm[i]] = newGroup[perm[i - 1]] + 1;
			else
				newGroup[perm[i]] = newGroup[perm[i-1]];
		group = newGroup;
	}
	return perm;
}
vector<int>getLCP(const string& s, const vector<int>& sa) {
	int n = s.size();
	vector<int>lcp(n);
	vector<int>pos(n);
	for (int i = 0; i < n; ++i)
		pos[sa[i]] = i;
	for (int i = 0, k = 0; i < n; ++i, k = max(k - 1, 0)) {
		if (pos[i] == n - 1) continue;
		for (int j = sa[pos[i] + 1]; s[i + k] == s[j + k]; ++k);
		lcp[pos[i]] = k;
	}
	return lcp;
}
int main()
{
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string s;
	cin >> s;
	int n = s.size();
	vector<int>SA = getSA(s);
	vector<int>lcp = getLCP(s, SA);
	for (int i = 0; i < n; ++i) cout << SA[i]+1 << " ";
	cout << "\nx ";
	for (int i = 0; i < n-1; ++i) cout << lcp[i] << " ";
	return 0;
}

-----------------------------------------------------------------------------
    
//정답코드    
    

#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
struct Comparator {
	const vector<int>& group;
	int t;
	Comparator(const vector<int>& _group, int _t) : group(_group), t(_t) {
	}
	bool operator() (int a, int b) {
		if (group[a] != group[b]) return group[a] < group[b];
		return group[a + t] < group[b + t];
	}
};
vector<int> getSuffixArray(const string& s) {
	int n = s.size();
	int t = 1;
	vector<int> group(n + 1);
	for (int i = 0; i < n; i++) group[i] = s[i];
	group[n] = -1;
	vector<int> perm(n);
	for (int i = 0; i < n; i++) perm[i] = i;
	while (t < n) {
		Comparator compareUsing2T(group, t);
		sort(perm.begin(), perm.end(), compareUsing2T);
		t *= 2;
		if (t >= n)
			break;
		vector<int> newGroup(n + 1);
		newGroup[n] = -1;
		newGroup[perm[0]] = 0;
		for (int i = 1; i < n; i++)
			if (compareUsing2T(perm[i - 1], perm[i]))
				newGroup[perm[i]] = newGroup[perm[i - 1]] + 1;
			else
				newGroup[perm[i]] = newGroup[perm[i - 1]];
		group = newGroup;
	}
	return perm;
}
vector<int> LCPArray(const string & S, const vector<int> & suffixArray) {
	int N = S.size();
	vector<int> ret(N, 0);
	vector<int>pos(N, 0);
	for (int i = 0; i < N; i++)
		pos[suffixArray[i]] = i;
	for (int i = 0, k = 0; i < N; i++, k = max(k - 1, 0)) {
		if (pos[i] == N - 1) continue;
		for (int j = suffixArray[pos[i] + 1]; S[i + k] == S[j + k]; k++);
		ret[pos[i]] = k;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string temp;
	cin >> temp;
	vector<int> suffix = getSuffixArray(temp);
	vector<int> LCP = LCPArray(temp, suffix);
	int N = temp.size();
	for (int i = 0; i < N; i++) {
		cout << suffix[i] + 1 << " ";
	}
	cout << "\nx ";
	for (int i = 0; i < N - 1; i++) {
		cout << LCP[i] << " ";
	}
	return 0;
}

dsa2341 4년 전 0

comparator 안에 vector 참조자 차이였네요..

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

문제

문제

출처

ICPC

고수님들 두 코드의 차이점을 알려주세요

dsa2341 4년 전 0

dsa2341 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말