K번째 문자열

1. 위의 K번째 문제 2. 오케이 3. 퀵소트 돌리고 4. 공통 문자열 검사를 진행하고 5. 그 다음에 걸르고 걸러서 K번째를 찾아내면 됨

#include <stdio.h> #define swap(a,b,t) (t=a, a=b, b=t) #define MAX 10 char str[MAX]; int idxL[MAX]; int lcp[MAX]; void idx_quicksort(int, int); int _strcmp(char*, char*); int main() { freopen("input.txt", "r", stdin); int T, test_case; int K; int len; int i, j; setbuf(stdout, NULL); scanf("%d", &test_case); for (T = 1; T <= test_case; ++T) { len = 0; scanf("%d", &K); scanf("%s", str); while (str[++len] != '\0'); for (i = 0; i < len; ++i) { idxL[i] = i; lcp[i] = 0; } idx_quicksort(0, len - 1); for (i = 1; i < len; ++i) { for (j = 0; (j < len - idxL[i]) && (j < len - idxL[i - 1]); ++j) { if (str[idxL[i - 1] + j] != str[idxL[i] + j]) // 서로 같으면 for문을 계속해서 돌음 break; } lcp[i] = j; // 같은 문자 반복을 피하기 위함 } for (i = 0; i < len; ++i) { if (K > len - idxL[i] - lcp[i]) K -= (len - idxL[i] - lcp[i]); else { str[idxL[i] + lcp[i] + K] = '\0'; // 끝자락을 마무리로 만듬 K = 0; break; } } if (K > 0) printf("#%d none\n", T); else printf("#%d %s\n", T, str + idxL[i]); } return 0; } void idx_quicksort(int left, int right) { int l = left + 1, r = right; int pivot = idxL[left]; int tmp; int i; if (left < right) { while (l <= r) { while ((l <= r) && (_strcmp(str + pivot, str + idxL[l]) >= 0)) ++l; while ((l <= r) && (_strcmp(str + pivot, str + idxL[r]) <= 0)) --r; if (l < r) swap(idxL[l], idxL[r], tmp); } swap(idxL[left], idxL[r], tmp); idx_quicksort(left, r - 1); idx_quicksort(r + 1, right); } } int _strcmp(char* str1, char* str2) { while ((*str1 == *str2) && (*str1 != '\0')) { ++str1; ++str2; } return *str1 - *str2; }