문제 소개
문자열 s와 또 다른 문자열 t가 주어져 있고, t는 s의 부분 수열(subsequence)이라고 가정해 봅시다. 이때 우리가 해야 할 일은, s에서 하나의 연속된 부분 문자열(substring)을 제거한 후에도 여전히 t가 s의 부분 수열로 남아 있도록 하면서, 제거할 수 있는 부분 문자열의 최대 길이를 구하는 것입니다.
예를 들어 입력이 s = "xyzxyxz", t = "yz"라고 한다면, 출력은 4가 됩니다. 인덱스 2부터 5까지의 부분 문자열 "zxyx"를 제거하면 남는 문자열은 "xyz"가 되고, 이 안에는 여전히 "yz"가 부분 수열로 존재하기 때문입니다.
참고로 부분 수열(subsequence)은 문자열에서 일부 문자를 건너뛰더라도 원래의 상대적인 순서가 유지되는 문자열을 의미하고, 부분 문자열(substring)은 반드시 연속된 형태여야 한다는 점이 다릅니다.
해결 접근 방법
이 문제는 그리디(Greedy) 탐색을 두 방향으로 수행하여 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- t의 각 문자를 s에서 왼쪽부터 최대한 앞쪽에 배치했을 때의 위치(left 배열)
- t의 각 문자를 s에서 오른쪽부터 최대한 뒤쪽에 배치했을 때의 위치(right 배열)
두 배열을 비교하면, 인접한 매칭 위치 사이의 간격 중 가장 넓은 구간이 곧 제거 가능한 후보가 됩니다. 구체적인 단계는 다음과 같습니다.
- left 리스트와 right 리스트를 생성하고, c1 = c2 = c3 = -1로 초기화합니다.
- s를 왼쪽에서 오른쪽으로 순회하며 t와 일치하는 문자를 만날 때마다 해당 인덱스를 left에 추가합니다. 모든 t의 문자가 매칭되면, 마지막 매칭 위치 이후의 남은 문자 개수를 c1에 저장하고 종료합니다.
- 이번에는 s를 오른쪽에서 왼쪽으로 순회하며 같은 작업을 수행하고, 일치하는 인덱스를 right의 앞에 삽입합니다. 모든 매칭이 끝나면 첫 번째 매칭 위치 앞의 문자 개수를 c2에 저장합니다.
- left[i]와 right[i+1] 사이의 간격(right[i+1] - left[i] - 1)을 계산하여 그 최댓값을 c3에 저장합니다.
- 최종적으로 c1, c2, c3 중 최댓값을 반환합니다.
예제 코드 (Python)
다음 구현을 통해 더 잘 이해해 보겠습니다.
class Solution: def solve(self, s, t): left = [] right = [] c1 = -1 c2 = -1 c3 = -1 j = 0 for i in range(len(s)): if s[i] == t[j]: left.append(i) j += 1 if j == len(t): c1 = len(s) - i - 1 break j = len(t) - 1 for i in range(len(s) - 1, -1, -1): if s[i] == t[j]: right.insert(0, i) j -= 1 if j == -1: c2 = i break for i in range(len(t) - 1): c3 = max(c3, right[i + 1] - left[i] - 1) return max(c1, c2, c3) ob = Solution() s = "xyzxyxz" t = "yz" print(ob.solve(s, t))
입력
"xyzxyxz", "yz"
출력
4
동작 과정 살펴보기
위 예제에서 왼쪽 탐색 결과 left = [1, 2]가 되어 c1 = 7 - 2 - 1 = 4입니다. 오른쪽 탐색 결과 right = [4, 6]이 되어 c2 = 4입니다. 또한 right[1] - left[0] - 1 = 6 - 1 - 1 = 4이므로 c3 = 4입니다. 따라서 세 값 중 최댓값인 4가 정답이 됩니다.
이 알고리즘은 문자열을 앞뒤로 각각 한 번씩만 순회하므로 시간 복잡도는 O(n)이며, n은 문자열 s의 길이입니다. 공간 복잡도 역시 t의 길이에 비례하는 O(m)으로 매우 효율적입니다.