[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 접미사 배열 (11656)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 접미사 배열 (11656)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 접미사 배열 (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의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

 

---

[ 코드 ]

#include<iostream>
#include<vector>
#include<string>
#include<algorithm> // sort 함수 포함
using namespace std;

int main() {
	string S; // 문자열
	cin >> S;

	int len = S.length(); // 문자열의 길이
	 // 문자열의 길이는 1000보다 작거나 같다 (길이가 1000이더라도, 1000개까지만 담는 것)
	
	 //vector <string> arr; // vector 정의
	string arr[1001];

	for (int i = 0; i < len; i++)
	{
		// arr.push_back(S.substr(i, len));
		// 문자열의 i~len까지의 길이를, arr마지막 원소(배열)에 추가
		// vector 배열일 경우에는 무조건, push_back을 사용해 줘야 함.

		 arr[i] = S.substr(i);//안되는 이유는?
	}

	sort(arr, arr + len); // 오름차순 정렬 실행
	
	//sort(arr.begin(), arr.end()); // vector 사용 경우 이렇게 정렬 

	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << '\n';
	}
	return 0;
}