길이가 같은 두 문자열 s와 t가 주어졌을 때, 이 두 문자열이 특정 조건을 만족하는 '동등한(equivalent)' 관계인지 판별하는 문제입니다. 동등 여부는 다음 규칙에 따라 결정됩니다.
동등성 판별 조건
- 두 문자열이 완전히 동일한 경우
- 또는, s를 같은 크기의 연속된 두 부분 문자열 s1, s2로 나누고, t도 같은 방식으로 t1, t2로 나누었을 때 아래 중 하나라도 성립하는 경우
- s1과 t1이 재귀적으로 동등하고, s2와 t2가 재귀적으로 동등한 경우
- s1과 t2가 재귀적으로 동등하고, s2와 t1이 재귀적으로 동등한 경우
예시로 이해하기
예를 들어 s = "ppqp", t = "pqpp"라고 해보겠습니다. s를 반으로 나누면 s1 = "pp", s2 = "qp"가 되고, t를 나누면 t1 = "pq", t2 = "pp"가 됩니다. 여기서 s1 = t2가 성립하고, 남은 s2("qp")와 t1("pq")을 각각 한 번 더 나누면 s21 = "q", s22 = "p", t11 = "p", t12 = "q"가 되어 s21 = t12, s22 = t11 역시 성립합니다. 따라서 두 문자열은 재귀적으로 동등하므로 결과는 True입니다.
해결 접근 방법
핵심 아이디어는 각 문자열을 정규 형태(canonical form)로 변환한 뒤 단순 비교하는 것입니다. 문자열을 계속 반으로 나누면서, 두 절반을 이어 붙였을 때 사전순으로 더 작은 조합을 선택하면 절반이 서로 뒤바뀌어 있더라도 항상 동일한 형태로 수렴하게 됩니다. 구체적인 절차는 다음과 같습니다.
- 문자열 s를 인자로 받는 util() 함수를 정의합니다.
- s의 길이가 홀수라면 더 이상 나눌 수 없으므로 s를 그대로 반환합니다.
- 그렇지 않다면 왼쪽 절반과 오른쪽 절반에 대해 각각 util()을 재귀 호출합니다.
- (left + right)와 (right + left) 중 사전순으로 더 작은 값을 반환합니다.
- 메인 함수에서는 util(s)와 util(t)가 같은지 비교한 결과를 반환합니다.
구현 코드
def util(s): if len(s) & 1 != 0: return s left = util(s[0:int(len(s) / 2)]) right = util(s[int(len(s) / 2):len(s)]) return min(left + right, right + left) def solve(s,t): return util(s) == util(t) s = "ppqp" t = "pqpp" print(solve(s, t))
실행 결과
입력:
"ppqp", "pqpp"
출력:
True
코드 설명 및 복잡도
len(s) & 1은 비트 AND 연산을 이용해 길이가 홀수인지 검사하는 효율적인 방법입니다. 홀수 길이의 문자열은 더 이상 분할할 수 없으므로 재귀의 종료 조건이 됩니다. 매 재귀 단계마다 문자열 절반씩 줄어들어 재귀 깊이는 O(log n)이며, 각 단계에서 문자열 연결과 비교에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 재귀 호출 스택과 문자열 저장을 포함해 O(n)입니다.