백준 11656번 접미사 배열 // C++

문제

접미사 배열

접미사 배열은 문자열 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의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

---

풀이

접미사를 뽑아내기 위하여, 문자열끼리의 더하기 연산자를 사용하였다.

뒤에서부터 하나씩 뽑아내야하기 때문에, input[i] + temp 와 같이 연산을 하였다.

다 풀고 나서 든 생각인데, 그냥 문자열의 제일 앞 부터 하나씩 지우면서 벡터에 추가했어도 됐을거 같다...

---

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    string input;

    cin >> input;

    vector<string> v;

    string temp = "";

    for (int i = input.length() - 1; i >= 0; i--) {
        temp = input[i] + temp;
        v.push_back(temp);
    }

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

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

    return 0;
}