[SWEA][Python3] 1256. [S/W 문제해결 응용] 6일차 - K번째 접미어

나의 풀이 :

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))