길이가 n인 두 문자열 s와 t가 있다고 가정해 봅시다. 우리는 s에서 한 문자를, t에서 다른 문자 하나를 골라 서로 교환할 수 있으며, 교환 횟수에는 제한이 없습니다. 이때 두 문자열을 동일하게 만들 수 있는지 확인하는 것이 목표입니다.
예를 들어 입력이 s = "xy", t = "yx"라면 출력은 True가 됩니다. 'x'와 'y'를 한 번만 교환해도 두 문자열을 일치시킬 수 있기 때문입니다.
해결 접근 방법
이 문제의 핵심 아이디어는 간단합니다. 두 문자열을 합쳤을 때 모든 문자가 짝수 번씩 등장해야만 교환을 통해 두 문자열을 동일하게 만들 수 있습니다. 어떤 문자가 전체에서 홀수 개만 존재한다면, 아무리 교환해도 두 문자열에 균등하게 나누어 담을 수 없기 때문입니다.
따라서 다음 단계로 문제를 해결할 수 있습니다.
- s와 t를 연결한 뒤 정렬하여 st를 만듭니다.
- 인덱스 0부터 st의 길이 - 1까지 2씩 증가시키며 반복합니다.
- st[i]와 st[i+1]이 다르면 False를 반환합니다.
- 모든 쌍이 일치하면 True를 반환합니다.
구현 예제
class Solution:
def solve(self, s, t):
st = sorted(s + t)
for i in range(0, len(st), 2):
if st[i] != st[i+1]:
return False
return True
ob = Solution()
print(ob.solve("xy", "yx"))
입력
"xy", "yx"
출력
True
동작 원리 살펴보기
"xy"와 "yx"를 연결하면 "xyyx"가 되고, 이를 정렬하면 "xxyy"가 됩니다. 인덱스 0과 1은 모두 'x', 인덱스 2와 3은 모두 'y'로 깔끔하게 쌍을 이루므로 True가 반환됩니다.
반면 s = "xy", t = "xz"인 경우를 생각해 보면, 연결 후 정렬한 결과는 "xx yz" 순서의 "xx yz"... 즉 'x', 'x', 'y', 'z'가 됩니다. 마지막 쌍에서 'y'와 'z'가 일치하지 않으므로 False가 반환되어, 교환으로는 두 문자열을 같게 만들 수 없음을 알려 줍니다.
이 알고리즘의 시간 복잡도는 정렬이 지배하므로 O(n log n)이며, 공간 복잡도는 연결된 문자열을 저장해야 하므로 O(n)입니다. 문자 빈도를 세는 Counter를 활용하면 O(n) 시간에도 해결할 수 있습니다.