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보다 작거나 같다.

풀이:

• 이 문제를 풀기 위해서는 문자열을 저장 할 수 있는 배열이 필요하다. 그리고 그 문자열을 하나씩 더하기 연산으로 저장해주면 된다. 이중 for문을 이용하여 앞에 접두사를 하나씩 줄여준다.
• 저장을 완료한 뒤에는 sort 함수를 이용하여 배열을 알파벳 순(ASCII 코드 순)으로 정렬 해준다. 이때 sort(배열 시작점(그냥 배열 넣으면 됨), 정렬할려는 배열 마지막 부분)으로 적어주면 된다.

코드:

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	string word, answer[1000];
	//입력 
	getline(cin, word);
	for(int i = 0; i < word.size(); i++){
		//i부터 시작함으로써 앞에 접두사를 날릴 수 있음 
		for(int j = i; j < word.size(); j++){
			//정답에 문자 한개 저장 
			answer[i] += word[j];
		}
	}
	//알파벳 순으로 정렬 #include <algorithm> 필요함 
	sort(answer, answer+word.size());
	//출력
	for(int i = 0; i < word.size(); i++){
		cout<<answer[i]<<endl;
	}
}