[BOJ] 11656 "접미사 배열" 문제 풀이 & 소스 코드 with C/C++

#INFO

난이도 : SIVLER4

문제 출처 : https://www.acmicpc.net/problem/11656

11656번: 접미사 배열

---

#SOVLE

문자열을 입력받고 문자열의 모든 접미사를 배열에 저장한 후 , 정렬해 주는 간단한 문자열 관련 문제이다.

문자열의 길이만큼 이중 for문을 돌려서 모든 접미사들을 접미사 배열 (dic 벡터) 에 저장한다.

	string str;
	cin >> str;
	vector<string> dic;
	for (int i = 0; i < str.length(); ++i) {
		string tempStr;
		for (int j = i; j < str.length(); ++j) {
			tempStr += str[j]; 
		}
		dic.push_back(tempStr);
	}

다음으로 sort 정렬함수를 이용해 dic 벡터에 저장된 접미사 문자열들을 사전순으로 정렬한 뒤 , 출력하면 된다.

	sort(dic.begin(), dic.end());
	
	for (int i = 0; i < dic.size(); ++i) {
		cout << dic[i] << " " << "\n";
	}

 

... 다른 좋은 풀이가 있나 구글링을 해 보았는데, 대부분 string 라이브러리의 substr() 함수를 이용하는 것 같았다.

substr() 함수란 인덱스 2개 (시작, 끝)을 지정해서 지정한 범위 만큼의 문자열을 반환해 주는 함수이다.

예를들어 str.substr(3) 이라고 선언하면, str 문자열의 3번째 인덱스 부터 끝까지 문자열을 잘라서 반환해준다.

확실히 아래처럼 substr() 함수를 이용하면 보다 코드가 깔끔해 지는 것 같기는 하다.

	for (int i = 0; i < str.length(); ++i) {
		string temp = str.substr(i);
		dic.push_back(temp);
	}

 

속도를 비교해보니, 이중for문을 사용해 직접 구현하는 것 보단 substr()함수를 이용하는 편이 2배 빨랐다.

 

* 이중for문 - 8ms

* substr() - 4ms

---

#SOLVE1 - 이중FOR

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

int main() {
	string str;
	cin >> str;
	vector<string> dic;
	for (int i = 0; i < str.length(); ++i) {
		string tempStr;
		for (int j = i; j < str.length(); ++j) {
			tempStr += str[j]; 
		}
		dic.push_back(tempStr);
	}

	sort(dic.begin(), dic.end());
	
	for (int i = 0; i < dic.size(); ++i) {
		cout << dic[i] << " " << "\n";
	}
	
	return 0;
}

#SOLVE2 -substr()

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

int main() {
	string str;
	cin >> str;
	vector<string> dic;
	
	for (int i = 0; i < str.length(); ++i) {
		string temp = str.substr(i);
		dic.push_back(temp);
	}
	
	sort(dic.begin(), dic.end());
	
	for (int i = 0; i < dic.size(); ++i) {
		cout << dic[i] << " " << "\n";
	}
	
	return 0;
}

---