두 문자열이 동형(isomorphic) 관계인지 확인해야 하는 경우가 있습니다. 여기서 '동형'이란 한 문자열의 각 문자를 일관된 규칙으로 다른 문자에 대응시켰을 때 두 번째 문자열과 정확히 일치하는지를 의미합니다. 예를 들어 'egg'와 'add'는 e→a, g→d라는 대응 규칙으로 동형 관계입니다.
이를 확인하려면 두 개의 문자열을 매개변수로 받는 함수를 정의하고, 문자열의 길이만큼 반복하면서 ord() 메서드를 사용해 각 문자를 정수(아스키 코드 값)로 변환하여 매핑 정보를 저장하면 됩니다. 또한 길이가 다른 두 문자열은 애초에 동형일 수 없으므로 사전에 검사하여 False를 반환합니다.
예제 코드
다음은 두 문자열이 동형인지 확인하는 전체 코드입니다.
MAX_CHARS = 256
def check_isomorphic(str_1, str_2):
len_1 = len(str_1)
len_2 = len(str_2)
# 길이가 다르면 동형일 수 없음
if len_1 != len_2:
return False
marked = [False] * MAX_CHARS # 이미 사용된 문자 표시용
map = [-1] * MAX_CHARS # 문자 매핑 정보 저장용
for i in range(len_2):
if map[ord(str_1[i])] == -1:
# str_2[i]가 이미 다른 문자와 매핑되어 있다면 실패
if marked[ord(str_2[i])] == True:
return False
marked[ord(str_2[i])] = True
map[ord(str_1[i])] = str_2[i]
elif map[ord(str_1[i])] != str_2[i]:
# 기존 매핑과 다른 대응이 나타나면 실패
return False
return True
str_1 = 'aababa'
str_2 = 'xxyyxx'
print("첫 번째 문자열 :")
print(str_1)
print("두 번째 문자열 :")
print(str_2)
print("'aab'과 'xxy'는 동형인가요?")
print(check_isomorphic("aab", "xxy"))
print("'aab'과 'xyz'는 동형인가요?")
print(check_isomorphic("aab", "xyz"))실행 결과
첫 번째 문자열 : aababa 두 번째 문자열 : xxyyxx 'aab'과 'xxy'는 동형인가요? True 'aab'과 'xyz'는 동형인가요? False
코드 설명
check_isomorphic이라는 이름의 함수를 정의하며, 이 함수는 두 개의 문자열을 매개변수로 받습니다.함수 내부에서 먼저 두 문자열의 길이를 계산합니다. 길이가 서로 다르면 동형일 수 없으므로 즉시
False를 반환합니다.크기가 256인 두 개의 리스트를 생성합니다. 하나는 이미 매핑에 사용된 문자를 표시하는
marked(False로 초기화), 다른 하나는 실제 문자 대응 정보를 저장하는map(-1로 초기화)입니다.문자열의 길이만큼 반복하면서
ord()메서드로 첫 번째 문자열의 각 문자를 정수 인덱스로 변환합니다.해당 문자가 아직 매핑되지 않았다면(-1인 경우), 두 번째 문자열의 문자가 이미 다른 문자에 사용 중인지 확인한 후, 사용 가능하면 새로운 매핑을 등록합니다.
이미 매핑된 문자라면 기존 대응 값과 현재 문자가 일치하는지 비교하고, 일치하지 않으면
False를 반환합니다.모든 문자가 일관된 규칙으로 대응되면 최종적으로
True를 반환합니다.함수 외부에서 두 개의 문자열을 정의하고 콘솔에 출력한 뒤, 이 문자열들을 인자로 전달하여 함수를 호출합니다.
호출 결과(True/False)가 콘솔에 출력됩니다.
정리
이 알고리즘은 시간 복잡도 O(n)으로 두 문자열을 한 번씩 순회하며 매핑의 일관성만 검사하기 때문에 효율적입니다. 'aab'과 'xxy'처럼 a→x, b→y라는 일관된 대응이 성립하면 True가 반환되고, 'aab'과 'xyz'처럼 같은 문자가 서로 다른 문자에 대응되어야 하는 경우에는 False가 반환됩니다.