[ BOJ ] 11656 : 접미사 배열 ( SILVER 4 ) / C, Python

문제

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

풀이 과정

한 문자열의 길이가 최대 1,000 이라면, 나올 수 있는 접미사의 개수는 최대 1,000 개 이다.

abcde 의 접미사는 abcde, bcde, cde, de, e 인 것처럼 말이다.

 

이러한 접미사의 정보를 모두 저장한 뒤, 이를 사전순으로 정렬하여 출력한다.

 

C언어에서 접미사를 추출하는 과정에서 애를 먹는다면, 포인터 연산을 활용하여 문자열의 시작 지점을 유리하게 선정하면 쉽게 접미사를 얻을 수 있다.

C

#include <stdio.h>
#include <string.h>

char str[1005];
char arr[1005][1005];
int main(void) {
    scanf("%s", str);
    int strSize = strlen(str);
    for (int i = 0; i < strSize; i++) {
        char* ptr = str+i;
        strcpy(arr[i], ptr);
    }

    // Selection Sort
    for (int i = 0; i < strSize - 1; i++) {
        int min = i;
        for (int j = i + 1; j < strSize; j++) {
            if (strcmp(arr[min], arr[j]) > 0) min = j;
        }

        if (min != i) {
            char tmp[1005];
            strcpy(tmp, arr[min]);
            strcpy(arr[min], arr[i]);
            strcpy(arr[i], tmp);
        }
    }

    for (int i = 0; i < strSize; i++) printf("%s\n", arr[i]);
    return 0;
}

Python

import sys
input = sys.stdin.readline

string = input().rstrip()
arr = []
for i in range(len(string)):
    arr.append(string[i:])

arr.sort()
for a in arr: print(a)