A응실 K번재 문자열 / q_sort, 아이디어

1. K번째 문자열 2. q_sort 3. 부분 문자열에 대한 아이디어 체크 4. 전 문제와 코드는 동일 5. 부분 문자열에 대한 아이디어만 추가

//#define MAX 1000 #define MAX 10 #include <stdio.h> int K; char src[MAX]; int num[MAX]; int str_len(char * s) { int n = 0; while (s[n]) n++; return n; } int str_cmp(char * a, char * b) { while (*a || *b) { if (*a != *b) return *a - *b; a++; b++; } return 0; } int str_cnt(char *a, char *b) { int rtn = 0; while (*a != '$' && *b != '$') { if (*a != *b) break; rtn++; a++; b++; } return rtn; } void q_sort(int s, int e) { int T, L, P = e, tmp; if (s >= e) return; for (L = s, T = s; L < e; L++) { if (str_cmp(&src[num[L]], &src[num[P]]) < 0) { if (L != T) { tmp = num[L]; num[L] = num[T]; num[T] = tmp; } T++; } } if (T != P) { tmp = num[T]; num[T] = num[P]; num[P] = tmp; } q_sort(s, T - 1); q_sort(T + 1, e); } int main(void) { freopen("input.txt", "r", stdin); int T; scanf("%d", &T); for (int t = 1; t <= T; t++) { int s; scanf("%d%s", &K, src); int l = str_len(src); for (int i = 0; i < l; i++) num[i] = i; q_sort(0, l - 1); for (int i = 0; i < l; i++) { int tmp; s = i; if (i == 0) tmp = l - num[i]; else tmp = l - num[i] - str_cnt(src + num[i], src + num[i - 1]); if (K <= tmp) { src[l + K - tmp] = '\0'; break; } K -= tmp; } printf("#%d ", t); if (s == l) printf("none\n"); else printf("%s\n", &src[num[s]]); } return 0; }