[SWEA] K번째 접미어 - Trie, vector, substr(), emplace_back()

K번째 접미어

두 가지 방법이 있다.
Trie를 사용하는 법과 vector words에 문자열을 substr()을 활용해 쪼갠 뒤 정렬하는 방법이다.

배운점

1.trie는 문자열의 입력과 동시에 정렬해주는 효과를 가진다. 또한 시간복잡도 측면에서도 vector를 사용하는 방법보다 효율적이다.(구현이 어렵다ㅜㅜ)
2.malloc을 통해 할당 받으면 사용 뒤 꼭꼭꼭 free시키자.
3. vector 에 값을 추가하려면 push_back()도 있지만, 임시 객체의 생성,복사, 파괴의 과정이 없는 emplace_back()을 활용하면 더욱 효율적이다.
4. str.substr(2,5)의 의미는 str란 문자열에서 2번째 글자부터 5개를 뽑아낸다는 의미이다. 즉 str[2:2+5) 이다.
ex) string str="monster"이면 str.substr(2,5)는 "nster"

<Trie를 사용한 코드>

#include <iostream>
#include <malloc.h>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
int T, K, tot;
vector <char> ans;
struct NODE {
	int alpha[26 + 2];
	bool isEnd;
	NODE* next[26 + 2];
};
NODE * makeNode() {
	NODE *tmp = (NODE*)malloc(sizeof(NODE));
	for (int i = 0; i < 26; i++) {
		tmp->next[i] = 0; tmp->alpha[i] = 0;
	}
	tmp->isEnd = false;
	return tmp;
};

void push(NODE *root, string str, int s, int e) {
	NODE *tmp = root;
	if (s == e) {	tmp->isEnd = true; return;}
	if (!tmp->next[str[s] - 'a']) tmp->next[str[s] - 'a']=makeNode();
	tmp->alpha[str[s] - 'a'] += 1;
	push(tmp->next[str[s] - 'a'], str, s + 1, e);//재귀 형식
}

void find(NODE *root) {
	NODE *tmp = root;
	if (tmp->isEnd)tot++;
	if (tot == K)return;
	for (int i = 0; i < 26; i++) {
		if (tmp->next[i]) {
			ans.push_back(i + 'a');
			find(tmp->next[i]);
			if (tot == K)return;
			ans.pop_back();
		}
	}
}

void del(NODE *root) {
	NODE *tmp = root;
	for (int i = 0; i < 26; i++) {
		if (tmp->next[i]) del(tmp->next[i]);
	}
	free(tmp);
}

int main() {
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		string arr; tot = 0; ans.clear();
		scanf("%d", &K);
		cin >> arr;
		int len = strlen(arr.c_str());
		//cout << arr;
	
		NODE *root = makeNode();
		for (int i = 0; i < len; i++) {
			if (!root->next[arr[i] - 'a']) root->next[arr[i] - 'a'] = makeNode();
			root->alpha[arr[i] - 'a']++;
			push(root->next[arr[i] - 'a'], arr, i + 1, len);
		}
		find(root);
		del(root);
		printf("#%d ", tc);
		for (int i = 0; i < ans.size(); i++) cout << ans[i];
		printf("\n");
	}
	
	return 0;
}

<vector에 substr로 emplace_back한 코드>

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

int T=10, K;
string target;
string ans;
vector <string> words;
bool Solve() {
	int targetLength = target.length();
	for (int i = 0; i < targetLength; i++) {
		words.emplace_back(target.substr(i, targetLength - i));//임시 객체의 생성,복사,파괴과정X
	}
	sort(words.begin(), words.end());
	ans = words[K - 1];
	if (K<targetLength) return true;
	else return false;
}
int main() {
	for (int i = 1; i <= T; i++) {
		scanf("%d", &K);
		cin >> target;
		ans = ""; words.clear();
		bool ret=Solve();
		if(ret) cout << "#" << i << " " << ans<<endl;
		else cout << "#" << i << " " << "none\n";
	}
	return 0;
}