[Programmers] #181909 - 접미사 배열 [Java][C++][Python]

문제 링크

---

1. 아이디어

문자열의 접미사는 시작 인덱스로 구분되므로, 인덱스 0부터 마지막 인덱스까지 각 위치를 시작점으로 하는 부분 문자열을 전부 만들면 모든 접미사를 빠짐없이 얻을 수 있다. 문자열 길이가 최대 100으로 작아서, 접미사 배열을 선형 시간에 구성하는 알고리즘 없이도 접미사를 전부 만들어 정렬하는 방식으로 충분하다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N^2 \log N)$	$O(N^2)$

($N$ = 문자열의 길이)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public String[] solution(String my_string) {
        int n = my_string.length();
        String[] arr = new String[n];

        for (int i = 0; i < n; i++) {
            arr[i] = my_string.substring(i);
        }
        Arrays.sort(arr);

        return arr;
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<string> solution(string my_string) {
    vector<string> v;
    for (int i = 0; i < my_string.size(); i++) {
        v.push_back(my_string.substr(i));
    }
    sort(v.begin(), v.end());

    return v;
}

def solution(my_string):
    return sorted(my_string[i:] for i in range(len(my_string)))

---