문제 이해하기
n개의 문자열 str1, str2, str3, ..., strn이 주어져 있다고 가정해 보겠습니다. 여기서 substri는 stri가 가질 수 있는 모든 부분 문자열(substring)을 담고 있는 집합입니다. 이 모든 집합의 합집합을 substr_union이라고 정의할 때, 총 q개의 질의(query)가 주어지며, 각 질의에 대해 사전순(lexicographically)으로 정렬된 substr_union에서 해당 인덱스(1부터 시작)의 원소를 찾아야 합니다.
예를 들어, 문자열 리스트가 ['pqr', 'pqt']이고 질의가 [4, 7, 9]라고 하면, 출력은 ['pqt', 'qt', 't']가 됩니다.
첫 번째 문자열의 부분 문자열 집합은 subs_str_1 = {p, pq, pqr, q, qr, r}이며, 두 번째 문자열의 부분 문자열 집합은 sub_str_2 = {p, pq, pqt, q, qt, t}입니다.
이 두 집합의 합집합인 substr_union은 {p, pq, pqr, pqt, q, qr, qt, r, t}입니다.
따라서 인덱스 4, 7, 9에 있는 원소는 각각 'pqt', 'qt', 't'입니다.
접근 방식
모든 부분 문자열을 일일이 생성해 정렬하는 방법도 있지만, 문자열이 길어지면 부분 문자열의 수가 제곱에 비례해 급격히 늘어나 비효율적입니다. 더 영리한 방법은 접미사(suffix)를 활용하는 것입니다. 어떤 문자열의 부분 문자열은 반드시 그 문자열의 특정 접미사의 접두어이므로, 중복이 제거되고 정렬된 접미사 목록과 인접한 접미사 쌍의 최장 공통 접두사(LCP, Longest Common Prefix) 길이만 있으면 원하는 위치의 부분 문자열을 효율적으로 계산할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다 −
- lng_i() 함수를 정의합니다. 이 함수는 suff, lng, i를 매개변수로 받습니다.
- d := (suff, lng)를 묶은 새로운 zip 객체
- lo := 0, hi := 0으로 초기화
- d의 각 튜플 (suf, lng)에 대해 다음을 수행합니다.
- lng가 None이면 lng := 0으로 설정
- hi := hi + len(suf) - lng (현재 접미사가 새롭게 추가하는 부분 문자열 수를 누적)
- hi - 1 == i이면 suf 전체를 반환
- 그렇지 않고 hi - 1 > i이면, lng부터 len(suf)-1까지 순회하며 lo + p == i가 되는 지점을 찾아 suf[:q+1]을 반환
- lo := hi로 갱신한 뒤 다음 접미사로 진행
- 끝까지 조건에 맞는 원소를 찾지 못하면 False 반환
- hlp_ii() 함수를 정의합니다. 이 함수는 str1, str2를 받아 두 문자열의 공통 접두사 길이를 계산합니다.
- ub := min(len(str1), len(str2)), cnt := 0
- i를 0부터 ub 미만까지 순회하며 str1[i] == str2[i]이면 cnt를 1 증가시키고, 다르면 즉시 cnt 반환
- 반복이 끝나면 cnt 반환
- t_dict := 새 딕셔너리, suff := 새 리스트, lng := 새 리스트를 준비
- 주어진 각 문자열에 대해 가능한 모든 접미사를 생성하고, 아직 등장하지 않은 접미사만 suff에 추가하여 중복을 제거
- suff를 사전순으로 정렬
- 첫 번째 원소에는 None을 넣고, 이후에는 인접한 접미사 쌍 (suff[i-1], suff[i])에 대해 hlp_ii()로 계산한 LCP 길이를 lng에 저장
- 각 질의 q에 대해 lng_i(suff, lng, q-1)의 결과를 res에 추가한 후 res 반환
예제
다음 구현을 통해 더 자세히 이해해 보겠습니다 −
def lng_i(suff, lng, i):
d = zip(suff,lng)
lo = hi = 0
for suf, lng in d:
if lng is None:
lng = 0
hi += len(suf) - lng
if hi - 1 == i:
return suf
elif hi - 1 > i:
for p, q in enumerate(list(range(lng, len(suf)))):
if lo + p == i:
return suf[:q+1]
lo = hi
return False
def hlp_ii(str1,str2):
ub = min(len(str1), len(str2))
cnt = 0
for i in range(ub):
if str1[i] == str2[i]:
cnt += 1
else:
return cnt
return cnt
def solve(strings,q_list):
t_dict = {}
suff = []
lng = []
for str in strings:
for i in range(len(str)):
value = str[i:]
if value not in t_dict:
t_dict[value] = 1
suff.append(value)
suff.sort()
suff_len = len(suff)
for i in range(suff_len):
if i == 0:
lng.append(None)
else:
lng.append(hlp_ii(suff[i-1], suff[i]))
res = []
for q in q_list:
(res.append(lng_i(suff, lng, q-1)))
return res
print(solve(['pqr', 'pqt'], [4, 7, 9]))
입력
['pqr', 'pqt'], [4, 7, 9]
출력
['pqt', 'qt', 't']
동작 원리 살펴보기
'pqr'과 'pqt'에서 추출한 고유한 접미사를 사전순으로 정렬하면 [pqr, pqt, qr, qt, r, t]가 됩니다. 각 접미사가 바로 앞 접미사와 공유하는 공통 접두사 길이(lng)를 빼면, 해당 접미사가 새롭게 기여하는 부분 문자열의 개수를 알 수 있습니다.
- 'pqr' → p, pq, pqr (3개, 인덱스 1~3)
- 'pqt' → pqt (1개, 인덱스 4 / 'p', 'pq'는 앞에서 이미 포함)
- 'qr' → q, qr (2개, 인덱스 5~6)
- 'qt' → qt (1개, 인덱스 7)
- 'r' → r (1개, 인덱스 8)
- 't' → t (1개, 인덱스 9)
이렇게 누적된 순서가 곧 사전순으로 정렬된 substr_union이 되며, 질의 인덱스가 어느 접미사 구간에 속하는지만 확인하면 해당 위치의 부분 문자열을 즉시 얻을 수 있습니다. 덕분에 모든 부분 문자열을 메모리에 저장하지 않고도 질의에 답할 수 있습니다.