Python에서 한 문자열을 다른 문자열로 변환할 수 있는지 확인하는 방법

길이가 같은 두 문자열 str1과 str2가 주어져 있다고 가정해 보겠습니다. 이때 0회 이상의 변환 작업을 거쳐 str1을 str2로 바꿀 수 있는지 판별해야 합니다.

여기서 말하는 한 번의 변환이란, str1에 등장하는 특정 문자 하나를 선택하여 그 문자가 나타나는 모든 위치를 다른 소문자 영어 알파벳으로 일괄 변경하는 것을 의미합니다. 목표는 이러한 변환만으로 str1을 str2와 완전히 같게 만들 수 있는지 확인하는 것입니다.

예제로 이해하기

예를 들어 str1 = "aabcc", str2 = "ccdee"가 입력으로 주어진 경우 결과는 True입니다. 'c'를 'e'로, 'b'를 'd'로, 'a'를 'c'로 차례대로 변환하면 되기 때문입니다.

단, 변환 순서가 매우 중요하다는 점에 유의해야 합니다. 변환은 해당 문자의 모든 등장 위치를 한꺼번에 바꾸기 때문에, 잘못된 순서로 진행하면 원하는 결과를 얻을 수 없습니다.

해결 접근 방법

이 문제는 문자 간 매핑(mapping) 관계를 이용해 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

매핑 일관성 검사: str1의 각 문자는 str2의 정확히 하나의 문자로만 대응되어야 합니다. 같은 문자가 서로 다른 문자로 매핑되면 변환이 불가능하므로 False를 반환합니다.
여분 문자 확보: 'a'→'b', 'b'→'a'처럼 두 문자를 맞바꾸려면 임시로 사용할 세 번째 문자가 반드시 필요합니다. 따라서 str2에서 아직 사용되지 않은 문자가 최소 하나 남아 있어야 합니다. 만약 26개 알파벳이 모두 사용 중이라면(str1과 str2가 완전히 같은 경우는 제외) 변환이 불가능합니다.
동일 문자열 처리: str1과 str2가 처음부터 같다면 변환이 필요 없으므로 즉시 True를 반환합니다.

알고리즘 단계

str1 == str2이면 True를 반환합니다.
str1의 문자를 키로, str2의 문자를 값으로 하는 매핑 딕셔너리를 만듭니다.
두 문자열을 함께 순회하면서 이미 존재하는 매핑과 값이 다르면 False를 반환합니다.
str2에서 사용된 고유 문자의 개수를 센 뒤, 26개보다 적으면 True, 아니면 False를 반환합니다.

Python 구현 코드

class Solution(object):
    def canConvert(self, str1, str2):
        # 두 문자열이 같으면 변환이 필요 없음
        if str1 == str2:
            return True

        mapping = {}          # str1의 문자 -> str2의 문자 매핑
        used_in_str2 = set()  # str2에서 이미 사용된 문자 집합

        for c1, c2 in zip(str1, str2):
            if c1 in mapping:
                # 같은 문자가 서로 다른 문자로 매핑되면 변환 불가
                if mapping[c1] != c2:
                    return False
            else:
                mapping[c1] = c2
                used_in_str2.add(c2)

        # str2에서 모든 26개 알파벳이 사용 중이면
        # 사이클을 풀 임시 문자가 없으므로 변환 불가
        return len(used_in_str2) < 26


ob = Solution()
print(ob.canConvert("aabcc", "ccdee"))

입력

"aabcc", "ccdee"

출력

True

복잡도 분석

두 문자열을 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 공간 복잡도는 매핑과 집합에 저장되는 문자가 알파벳 26개로 제한되므로 O(1)입니다.