알파벳 소문자로 이루어진 두 개의 문자열 A와 B가 주어졌을 때, A에서 단 두 글자를 서로 바꿔(swap) B와 동일한 문자열을 만들 수 있는지 확인하는 문제입니다.
예를 들어 A = "ba", B = "ab"가 입력으로 주어지면, A의 첫 번째 글자 'b'와 두 번째 글자 'a'를 맞바꾸면 "ab"가 되므로 결과는 True입니다.
문제 해결 접근 방식
이 문제는 다음과 같은 순서로 판단하면 효율적으로 해결할 수 있습니다.
- 먼저 A와 B의 길이가 다르면 False를 반환합니다. 길이가 다른 문자열은 아무리 교환해도 같아질 수 없기 때문입니다.
- 두 문자열을 정렬했을 때 결과가 다르다면, 즉 구성 문자 자체가 다르다면 False를 반환합니다.
- A와 B가 완전히 같으면서 A 내부에 중복되지 않는 고유한 문자만 존재한다면 False를 반환합니다. 이 경우에는 서로 바꿀 수 있는 동일한 문자 쌍이 없어서 교환 시 반드시 달라지기 때문입니다.
- 위 조건에 해당하지 않는다면, 각 위치를 순회하면서 문자가 다른 지점의 개수를 셉니다. 이때 차이가 나는 지점이 3개 이상이 되면 False를 반환합니다(정확히 2곳만 달라야 한 번의 교환으로 일치시킬 수 있습니다).
- 모든 검사를 통과하면 True를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 구현 과정을 더 잘 이해할 수 있습니다.
class Solution:
def buddyStrings(self, A, B):
if len(A)!=len(B):
return False
elif sorted(A)!=sorted(B):
return False
elif A==B and len(set(A))==len(A):
return False
else:
count=0
for i in range(len(A)):
if A[i]!=B[i]:
count+=1
if count==3:
return False
return True
ob = Solution()
print(ob.buddyStrings("ba","ab"))
입력
"ba","ab"
출력
True
코드 설명
위 코드의 핵심 로직을 정리하면 다음과 같습니다.
len(A)!=len(B): 길이 불일치 여부를 가장 먼저 확인합니다.sorted(A)!=sorted(B): 정렬 결과를 비교해 두 문자열이 같은 문자들로 구성되어 있는지 검증합니다.A==B and len(set(A))==len(A): 두 문자열이 동일한 경우, set으로 중복을 제거한 길이와 원래 길이를 비교해 고유 문자만 있는지 확인합니다. 중복 문자가 있다면 그 문자끼리 바꿔도 여전히 같으므로 True가 됩니다.- 마지막으로 인덱스별로 비교하여 다른 위치가 정확히 2개인 경우에만 True를 반환합니다.
이 알고리즘의 시간 복잡도는 정렬 연산으로 인해 O(n log n), 공간 복잡도는 O(n)입니다.