반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. Sort

2. substring


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


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








소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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;
}
cs

반응형