두 개의 소문자 문자열 s와 t가 주어졌을 때, s의 각 문자를 다른 문자(동일한 문자일 수도 있음)에 1:1로 대응시켜 s를 t로 변환할 수 있는지 확인하는 문제입니다. 이때 문자들의 순서는 절대 바뀌지 않는다는 조건이 붙습니다.
예를 들어 입력이 s = "papa", t = "lili"라면 결과는 True가 됩니다. 'p' → 'l', 'a' → 'i'라는 매핑을 만들면 'papa'가 'lili'로 정확히 변환되기 때문입니다.
문제 해결 접근 방법
핵심 아이디어는 양방향 딕셔너리(bidirectional map)를 사용하는 것입니다. 한 문자가 이미 다른 문자로 매핑되어 있다면, 이후 같은 문자가 서로 다른 대상으로 매핑되려 할 때 충돌이 발생하므로 즉시 False를 반환하면 됩니다.
단계별 풀이
- 정방향 매핑을 저장할
s_dict와 역방향 매핑을 저장할t_dict를 생성합니다. i를 0부터s와t길이 중 작은 값까지 순회합니다.s[i]가 이미s_dict에 존재한다면, 저장된 매핑값이t[i]와 다를 경우 False를 반환합니다.- 그렇지 않고
t[i]가 이미t_dict에 존재한다면, 저장된 매핑값이s[i]와 다를 경우 False를 반환합니다. - 두 경우 모두 아니라면 새로운 매핑을 양방향으로 등록합니다.
- 모든 문자를 검사한 후 충돌이 없었다면 True를 반환합니다.
구현 예제 코드
class Solution:
def solve(self, s, t):
s_dict = {}
t_dict = {}
for i in range(min(len(s), len(t))):
if s[i] in s_dict:
if s_dict[s[i]] != t[i]:
return False
elif t[i] in t_dict:
if t_dict[t[i]] != s[i]:
return False
else:
s_dict[s[i]] = t[i]
t_dict[t[i]] = s[i]
return True
ob = Solution()
print(ob.solve("papa", "lili"))
입력
"papa", "lili"
출력
True
더 간결한 대안: 집합(Set) 활용하기
딕셔너리를 직접 관리하지 않고도 파이썬의 zip과 set을 조합하면 한 줄로 동일한 로직을 구현할 수 있습니다. 문자 쌍의 종류 수가 각 문자열의 고유 문자 수와 모두 일치하면 1:1 매핑이 성립합니다.
def solve(s, t):
return len(set(zip(s, t))) == len(set(s)) == len(set(t))
복잡도 분석
- 시간 복잡도: O(n) — 문자열을 한 번만 순회하며 각 검사는 상수 시간에 이루어집니다.
- 공간 복잡도: O(k) — k는 서로 다른 문자의 개수로, 최대 알파벳 크기인 26으로 제한됩니다.