[1256번] K번째 접미어

문제 출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18GHd6IskCFAZN&categoryId=AV18GHd6IskCFAZN&categoryType=CODE

알고리즘 분석 :

문제 해결에 필요한 사항

1. Sort

2. substring

substring을 모두 분리 시키고 난 뒤 sort(여기서는 merge sort)를 이용하여

substring을 사전순으로 나열시킨 후 k번째 값을 출력하면 된다.

소스 코드 : 

#include <iostream>
 
char str[402];
char strList[402][402];
char tmpList[402][402];
 
int _strlen(char *str) {
    int len = 0;
    while(str[++len]){}
    return len;
}
 
void _strcpy(char *str1, char *str2) {
    while (*str1++ = *str2++) {}
}
// 양수면 str1이 더 사전순으로 뒤에
int _strcmp(char *str1, char *str2) {
    int i = 0;
    while (str1[i]) {
        if (str1[i] != str2[i])
            break;
        i++;
    }
 
    return str1[i] - str2[i];
}
void _mergeSort(int s, int e) {
    if (s < e) {
        int m = (s + e) / 2;
        _mergeSort(s, m);
        _mergeSort(m + 1, e);
 
        int p = s;
        int q = m + 1;
        int idx = s;
        while (p <= m || q <= e) {
            if (q > e || (p <= m && _strcmp(strList[p], strList[q]) < 0))
                _strcpy(tmpList[idx++], strList[p++]);
            else
                _strcpy(tmpList[idx++], strList[q++]);
        }
 
        for (int i = s; i <= e; i++)
            _strcpy(strList[i], tmpList[i]);
    }
}
int main() {
    freopen("input.txt", "r", stdin);
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        int k;
        scanf("%d", &k);
 
        int strIdx = 0;
        scanf("%s", str);
 
        int len = _strlen(str);
        for (int i = 0; i < len; i++)
            _strcpy(strList[strIdx++], &str[i]);
 
        _mergeSort(0, len - 1);
 
        printf("#%d %s\n", tc, strList[k - 1]);
    }
 
    return 0;
}