알고리즘(C++) / 백준 11656 : 접미사 배열

11656

boj.kr/11656

11656번: 접미사 배열

 

문제

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.

baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.

문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.

 

출력

첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

 

코드

//11656 접미사 배열
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string S;
	cin >> S;

	vector <string> suffix;

	for (int i = 0; i < S.size(); i++) {
		string sub;
		for (int j = i; j < S.size(); j++) {

			sub += S[j];
		}
        //sub = S.substr(i, S.size());
		suffix.push_back(sub);
	}

	sort(suffix.begin(), suffix.end());

	for (int i = 0; i < suffix.size(); i++) {
		cout << suffix[i] << "\n";
	}

	return 0;
}

 

설명

suffix(접미사), string형 벡터를 생성한다. suffix 벡터에 문자열 S의 모든 접미사를 저장한다. 

algorithm헤더에 포함된 sort함수로 suffix 벡터를 정렬한다. 이때 정렬은 사전순으로 정렬되게 된다. 

 

구글링을 해보니 문자열을 일부 추출하는 함수인 substr가 존재한다. substr()을 이용해서도 문제를 풀 수 있다. 

 

결과

 

고찰

나처럼 구현하면 시간이 오래 걸리지 않을까 생각했다. 하지만 시간 짧지 않기 때문에 다음과 같이 구현할 수 있었다. 

 

난이도

◐○○○○