길이가 같은 두 문자열 s와 t가 있다고 가정해 봅시다. 여기서 수행할 수 있는 연산은 문자열 안에서 두 개의 인덱스를 선택하고(두 인덱스가 같아도 무방), 해당 위치의 문자를 서로 맞바꾸는(swap) 것입니다. 이때 정확히 하나의 문자열에 대해 최대 한 번의 문자 교환만 허용했을 때, 두 문자열을 완전히 동일하게 만들 수 있는지 판별하는 것이 문제의 핵심입니다.
예를 들어 입력이 s = "hello", t = "hlelo"라면 결과는 True입니다. 어느 한쪽 문자열에서 'e'와 'l'의 위치를 서로 바꾸면 두 문자열이 같아지기 때문입니다.
문제 해결 접근 방식
이 문제는 다음과 같은 논리로 해결할 수 있습니다.
- 허용되는 최대 차이 개수 max_diffs를 2로 설정합니다.
- 현재까지 발견된 차이 개수를 저장할 diffs를 0으로 초기화합니다.
- s의 문자들을 담을 집합 st와, t의 문자들을 담을 집합 st2를 각각 생성합니다.
- i를 0부터 s의 길이까지 순회하며 다음을 수행합니다.
- s[i]와 t[i]가 다르면 diffs를 1 증가시킵니다.
- s[i]가 st에 없으면 추가하고, t[i]가 st2에 없으면 추가합니다.
- 순회 중 diffs가 max_diffs(=2)를 초과하면 즉시 False를 반환합니다. 한 번의 교환으로는 세 곳 이상의 차이를 해결할 수 없기 때문입니다.
- 마지막으로 다음 조건을 모두 만족하면 True, 그렇지 않으면 False를 반환합니다.
- diffs가 0 또는 2인 경우 (0이면 이미 두 문자열이 동일하다는 뜻)
- st와 st2의 크기가 같고, 두 집합의 내용도 완전히 일치하는 경우 — 교환 대상 문자들이 서로 존재해야 실제로 자리를 바꿀 수 있기 때문입니다.
예제 코드
def solve(s, t):
max_diffs = 2
diffs = 0
st = set()
st2 = set()
for i in range(len(s)):
if s[i] != t[i]:
diffs += 1
if s[i] not in st:
st.add(s[i])
if t[i] not in st2:
st2.add(t[i])
if diffs > max_diffs:
return False
return (diffs == 0 or diffs == 2) and len(st) == len(st2) and st == st2
s = "hello"
t = "hlelo"
print(solve(s, t))입력
"hello", "hlelo"
출력
True
동작 원리 요약
이 알고리즘의 시간 복잡도는 O(n)으로, 문자열의 길이에 비례해 한 번만 순회하면 됩니다. 핵심 포인트는 다음과 같습니다.
- 차이가 0개: 두 문자열이 이미 동일하므로 교환이 필요 없습니다.
- 차이가 1개: 한 번의 교환으로 홀수 개의 위치 차이를 해결할 수 없으므로 False입니다.
- 차이가 2개: 두 위치의 문자들이 서로 교차해서 일치하는 경우에만(True ↔ True 형태) 교환으로 해결 가능합니다. 집합 비교(st == st2)가 이를 검증합니다.
- 차이가 3개 이상: 한 번의 교환으로는 절대 해결할 수 없으므로 조기에 False를 반환해 불필요한 연산을 줄입니다.