반응형
https://www.acmicpc.net/problem/11656
11656번: 접미사 배열
첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.
www.acmicpc.net
문제

먼저 하나씩 접미사로 만든 list의 값을 만들어야 된다고 생각했다.
시행착오
첫번째 접근은 bisect 을 사용하여 배열 이진 분할을 사용해서 진행할 수 있을까 생각을 했는데,
생각보다 제대로된 값이 나오지 않아서 bisect.bisect_left 함수에 대한 것을 알아보았다.
def bisect_left(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid+1
else: hi = mid
return lo
위의 코드를 다시 확인해본 결과,
이 함수는 "이미 주어진 값이 정렬되어있다는 가정하에"라는 것을 다시한번 확인해볼 수 있었다.
정답 코드
그러다가, sorted 함수에 대해서 생각이났다.
sorted를 사용하면, 문자열을 잘 정렬해줄텐데,,? 하고 적용해주었다.
input_string = input()
input_list = list()
for i in range(len(input_string)):
input_list.append(input_string[i:])
sorted_list = sorted(input_list)
for i in range(len(sorted_list)):
print(sorted_list[i])
성공!
꽤나 쉬운 문제었다.
반응형