나의 풀이 :

T = int(input())
for tc in range(1, T + 1):
K = int(input())
S = input()
words = [S[i:] for i in range(len(S))]
ans = sorted(words)[K-1] if K <= len(S) else 'none'
print('#{} {}'.format(tc, ans))


한마디 :

위 풀이는 그냥 모든 접미사를 다 구해놓고 정렬해서 K번째 접미사를 구한 것이다.


아래 풀이는 일단 a부터 z까지 각각 시작하는 접미사를 분류한 다음 K번째 접미사가 속해 있는 단어 집합에서만 정렬을 시도한다.


나의 풀이 2 :

T = int(input())
for tc in range(1, T + 1):
K = int(input())
S = input()
suffix = [[] for _ in range(26)]
for i, c in enumerate(S):
idx = ord(c)-ord('a')
suffix[idx].append(S[i:])
ans = 'none'
for i, words in enumerate(suffix):
if K > len(words):
K -= len(words)
else:
ans = sorted(words)[K-1]
break
print('#{} {}'.format(tc, ans))