문제 소개
두 개의 문자열이 주어졌다고 가정해 보겠습니다. 첫 번째 문자열의 길이는 두 번째 문자열보다 깁니다. 우리가 해야 할 일은 첫 번째 문자열에서 잘라낸 부분 문자열이 두 번째 문자열과 완전히 일치하는지, 아니면 단 한 위치만 다른지를 검사하고, 그러한 부분 문자열이 시작되는 인덱스를 모두 찾아내는 것입니다.
예를 들어 입력이 다음과 같다면:
string1 = 'tpoint', string2 = 'pi'
출력은 1 2가 됩니다.
그 이유를 살펴보면, 인덱스 1에서 시작하는 부분 문자열 'po'는 'pi'와 두 번째 글자만 다르고, 인덱스 2에서 시작하는 'oi'는 첫 번째 글자만 다릅니다. 즉, 두 위치 모두 "한 위치 차이" 조건을 만족하므로 정답에 포함되는 것입니다.
풀이 접근 방법: Z 알고리즘
이 문제는 Z 알고리즘(Z-algorithm)을 활용하면 효율적으로 해결할 수 있습니다. Z 알고리즘은 문자열의 각 위치에서 접두사와 일치하는 최장 길이를 선형 시간에 계산하는 기법입니다.
핵심 아이디어는 다음과 같습니다.
- 정방향 검색(fwd): 각 시작 위치에서 두 번째 문자열과 앞쪽부터 몇 글자까지 일치하는지 계산합니다.
- 역방향 검색(bwrd): 문자열을 뒤집어서 검색하면, 각 위치 기준 뒤쪽부터 몇 글자까지 일치하는지 계산할 수 있습니다.
- 정방향 일치 길이와 역방향 일치 길이의 합이 (두 번째 문자열 길이 − 1) 이상이면, 해당 위치에서 시작하는 부분 문자열은 최대 한 곳만 다르다는 의미입니다.
알고리즘 단계
search()함수를 정의합니다. 이 함수는 두 개의 문자열을 받아 Z 배열을 계산합니다.str_cat := string1 + string2처럼 두 문자열을 연결합니다.str_cat의 크기만큼 0으로 초기화된 새 리스트z_list를 만듭니다.z_list[0]은 전체 길이로 설정합니다.left와right포인터를 0으로 초기화합니다.- i를 1부터
str_cat의 끝까지 순회하며 다음을 수행합니다.- i가
right보다 크면 처음부터 직접 비교하여z_list[i]를 구하고, j가 0보다 크면left와right구간을 갱신합니다. - 그렇지 않으면 이미 계산된 값을 재활용합니다. 즉, k := i − left로 두고,
z_list[k]가 남은 구간 길이(r_len := right − i + 1)보다 작으면z_list[i] := z_list[k]로 설정합니다. - 그렇지 않으면 m := right + 1부터 추가 비교를 이어가며
z_list[i]를 확장하고,left와right를 갱신합니다.
- i가
- 매 반복마다
z_list[i]가 첫 번째 매개변수 문자열의 길이를 넘지 않도록 최솟값으로 제한합니다. z_list[len(string1):]슬라이스를 반환합니다.
fwd := search(str2, str1)로 정방향 일치 정보를 구합니다.bwrd := search(str2[::-1], str1[::-1])로 역방향 일치 정보를 구한 뒤 리스트를 뒤집습니다.- 결과 인덱스를 담을 빈 리스트
idx를 만듭니다. - i를 0부터 len(str1) − len(str2)까지 순회하면서,
fwd[i] + bwrd[i + len(str2) − 1] >= len(str2) − 1을 만족하면 i를idx에 추가합니다. idx가 비어 있으면False를 반환하고, 그렇지 않으면 인덱스들을 공백으로 구분한 문자열을 반환합니다.
예제 코드
아래 파이썬 구현을 보면 더 쉽게 이해할 수 있습니다.
def search(string1, string2):
str_cat = string1 + string2
z_list = [0] * len(str_cat)
z_list[0] = len(str_cat)
right = 0
left = 0
for i in range(1, len(str_cat)):
if i > right:
j = 0
while j + i < len(str_cat) and str_cat[j] == str_cat[j+i]:
j += 1
z_list[i] = j
if j > 0:
left = i
right = i + j - 1
else:
k = i - left
r_len = right - i + 1
if z_list[k] < r_len:
z_list[i] = z_list[k]
else:
m = right + 1
while m < len(str_cat) and str_cat[m] == str_cat[m - i]:
m += 1
z_list[i] = m - i
left = i
right = m - 1
z_list[i] = min(len(string1), z_list[i])
return z_list[len(string1):]
def solve(str1, str2):
fwd = search(str2, str1)
bwrd = search(str2[::-1], str1[::-1])
bwrd.reverse()
idx = []
for i in range(len(str1) - len(str2) + 1):
if fwd[i] + bwrd[i + len(str2) - 1] >= len(str2) - 1:
idx.append(str(i))
if len(idx) == 0:
return False
else:
return (" ".join(idx))
print(solve('tpoint', 'pi'))
입력
'tpoint', 'pi'
출력
1 2
시간 복잡도
Z 알고리즘은 문자열 길이에 대해 선형 시간 O(N + M)에 동작합니다. 따라서 이 풀이 역시 전체적으로 선형 시간에 실행되며, 모든 위치를 하나씩 brute-force로 비교하는 O(N × M) 방식보다 훨씬 효율적입니다. 문자열이 길어질수록 그 성능 차이는 더욱 커집니다.