파이썬으로 두 문자열을 분할해 각 파티션이 서로 아나그램이 되도록 만드는 방법

문제 정의

길이가 같은 두 개의 비어 있지 않은 문자열 s와 t가 있다고 가정해 봅시다. 우리는 이 문자열들을 여러 부분 문자열로 나누어야 하며, s의 각 조각과 t의 대응되는 조각은 반드시 같은 길이를 가져야 하고 서로 아나그램(anagram), 즉 같은 문자들로만 구성되어야 합니다.

목표는 이 조건을 만족하면서 잘라내기 지점(cut index)을 찾아 최대한 많은 수의 분할을 만드는 것입니다. 만약 가능한 방법이 없다면 빈 리스트를 반환하면 됩니다.

예시

입력이 다음과 같다고 해봅시다.

s = "bowcattiger", t = "owbactietgr"

이 경우 출력은 [0, 3, 5, 6, 10]이 됩니다. 문자열을 다섯 구간으로 나누면 각 쌍이 아나그램 관계가 되기 때문입니다.

s = ["bow", "ca", "t", "tige", "r"]
t = ["owb", "ac", "t", "ietg", "r"]

"bow"와 "owb", "ca"와 "ac", "tige"와 "ietg"처럼 각 조각은 글자 순서만 다를 뿐 동일한 문자로 이루어져 있습니다.

접근 방법

이 문제는 뒤에서부터 잘라낼 위치를 하나씩 검사하는 방식으로 효율적으로 해결할 수 있습니다. 전체 문자열에서 한 글자씩 제거해 가면서 남은 접두사 부분들의 문자 빈도수가 계속 일치하는지 확인하면, 그 시점마다 유효한 자르기 위치임을 알 수 있습니다.

구체적인 알고리즘 단계는 다음과 같습니다.

결과를 저장할 리스트 intervals를 생성합니다.
문자열 a의 문자별 빈도수를 담은 맵 ca를 만듭니다.
문자열 b의 문자별 빈도수를 담은 맵 cb를 만듭니다.
ca와 cb가 다르다면 두 문자열은 애초에 아나그램이 아니므로 빈 리스트를 반환합니다.
인덱스 x를 문자열 끝부터 시작하여 0까지 거꾸로 반복합니다.
- ca[a[x]]와 cb[b[x]]를 각각 1씩 감소시킵니다.
- 감소 후에도 ca == cb라면, 인덱스 x까지의 두 접두사가 아나그램 관계이므로 x를 intervals에 추가합니다.
intervals를 오름차순으로 정렬하여 반환합니다.

전체 문자열의 빈도수가 동일하므로, 뒤에서부터 제거해 가면서 빈도수가 일치하는 지점은 곧 유효한 경계선이 됩니다. 이 방식은 O(n) 시간 안에 모든 잘라내기 위치를 찾을 수 있어 매우 효율적입니다.

파이썬 구현 예제

from collections import Counter

class Solution:
    def solve(self, a, b):
        intervals = []
        ca = Counter(a)
        cb = Counter(b)
        
        # 두 문자열의 문자 구성이 다르면 불가능
        if ca != cb:
            return []
        
        # 뒤에서부터 한 글자씩 제거하며 확인
        for x in reversed(range(len(a))):
            ca[a[x]] -= 1
            cb[b[x]] -= 1
            if ca == cb:
                intervals.append(x)
        
        return sorted(intervals)

ob = Solution()
s = "bowcattiger"
t = "owbactietgr"
print(ob.solve(s, t))

입력

s = "bowcattiger"
t = "owbactietgr"

출력

[0, 3, 5, 6, 10]

정리

이 문제의 핵심은 Counter를 활용한 문자 빈도수 비교입니다. 두 문자열 전체가 아나그램이라는 사실이 먼저 확인되면, 뒤에서부터 접두사를 줄여 가며 빈도수가 일치하는 모든 지점을 찾으면 됩니다. 이렇게 찾은 인덱스들이 바로 최대 분할을 만드는 잘라내기 위치이며, 마지막에 정렬해서 반환하면 깔끔한 결과를 얻을 수 있습니다.