두 문자열 source와 target이 주어졌을 때, source의 부분 수열(subsequence)들을 여러 개 추출하여 이어 붙였을 때 target과 완전히 같은 문자열이 되도록 하는 최소 개수를 구하는 문제입니다. 만약 어떻게 조합해도 target을 만들 수 없다면 -1을 반환해야 합니다.
예를 들어 source = "xyz", target = "xyzyzz"가 입력으로 주어지면, ["xyz" + "yz" + "z"]처럼 세 개의 부분 수열을 이어 붙일 수 있으므로 출력은 3이 됩니다.
문제 해결 접근 방법
이 문제는 그리디(greedy) 방식으로 해결할 수 있습니다. 매번 source를 처음부터 끝까지 한 번 훑으면서, target에서 일치하는 문자를 최대한 많이 소모하는 것이 핵심 아이디어입니다.
- s_size := s의 길이, t_size := t의 길이로 초기화합니다.
- concat_count := 0, target_idx := 0으로 설정합니다.
- target_idx가 t_size보다 작은 동안 다음 과정을 반복합니다.
- source_idx := 0으로 초기화하고, temp_index에 현재 target_idx 값을 저장합니다.
- source_idx가 s_size보다 작고 target_idx가 t_size보다 작은 동안 반복하면서, s[source_idx]와 t[target_idx]가 같으면 target_idx를 1 증가시킵니다. 이후 source_idx를 1 증가시킵니다.
- 한 바퀴를 돈 뒤 temp_index와 target_idx가 같다면, 이번 순회에서 단 하나의 문자도 매칭되지 않았다는 의미이므로 -1을 반환합니다.
- 매칭에 성공했다면 concat_count를 1 증가시킵니다.
- 반복이 끝나면 concat_count를 반환합니다.
구현 예제
class Solution:
def solve(self, s, t):
s_size, t_size = len(s), len(t)
concat_count = 0
target_idx = 0
while target_idx < t_size:
source_idx = 0
temp_index = target_idx
while source_idx < s_size and target_idx < t_size:
if s[source_idx] == t[target_idx]:
target_idx += 1
source_idx += 1
if temp_index == target_idx:
return -1
concat_count += 1
return concat_count
ob = Solution()
source = "xyz"
target = "xyzyzz"
print(ob.solve(source, target))입력
"xyz", "xyzyzz"
출력
3
동작 원리 설명
첫 번째 순회에서 source인 "xyz"를 스캔하면 target의 앞부분 "xyz"가 매칭됩니다. 두 번째 순회에서는 "yz"가 매칭되고, 세 번째 순회에서 마지막 "z"가 매칭되어 총 3개의 부분 수열로 target을 완성할 수 있습니다.
만약 target에 source에 없는 문자가 포함되어 있다면, 한 번의 순회 동안 target_idx가 전혀 진행되지 않으므로(temp_index와 target_idx가 동일) 즉시 -1을 반환하여 불가능함을 알립니다.
이 알고리즘의 시간 복잡도는 O(t_size × s_size)이며, 각 순회마다 target의 인덱스가 최소 1칸씩 진행되므로 반복 횟수는 최대 t_size를 넘지 않습니다.