길이가 같은 두 개의 소문자 문자열 s와 t가 있다고 가정해 봅시다. 우리는 s에서 한 문자를, t에서 다른 문자 하나를 골라 서로 맞바꿀 수 있으며, 이 연산은 원하는 만큼 몇 번이든 반복할 수 있습니다. 최종적으로 이 두 문자열을 완전히 동일하게 만드는 것이 가능한지 판별해야 합니다.
예를 들어 입력이 s = "abcd", t = "cdab"라면 출력은 True가 됩니다.
문제 해결 접근 방법
핵심 아이디어는 간단합니다. 문자를 교환할 때마다 각 문자열에서 문자 하나씩이 이동하기 때문에, 특정 문자의 전체 등장 횟수는 항상 그대로 유지됩니다. 따라서 두 문자열을 합쳤을 때 모든 문자가 짝수 번 등장해야만 두 문자열을 같게 만들 수 있습니다.
- 1단계: s와 t를 이어 붙인 문자열에서 각 문자의 빈도수(fre)를 계산합니다.
- 2단계: 빈도수 목록의 각 값(cnt)을 순회하며 검사합니다.
- 3단계: cnt를 2로 나눈 나머지가 1이라면(즉, 홀수 빈도) False를 반환합니다.
- 4단계: 모든 빈도수가 짝수라면 True를 반환합니다.
예제 코드
다음 구현 예시를 통해 더 자세히 이해해 보겠습니다.
from collections import Counter
def solve(s, t):
fre = Counter(s + t)
for cnt in fre.values():
if cnt % 2:
return False
return True
s = "abcd"
t = "cdab"
print(solve(s, t))
입력
"abcd", "cdab"
출력
True
동작 원리 상세 설명
위 예제에서 s와 t를 합치면 "abcdcdab"가 되고, 각 문자 'a', 'b', 'c', 'd'는 정확히 2번씩 등장합니다. 모든 문자의 빈도수가 짝수이므로 결과는 True입니다. 반면 s = "abc", t = "abd"였다면 'c'와 'd'가 각각 1번만 등장하므로 False가 반환됩니다.
이 알고리즘은 파이썬의 Counter 클래스를 활용해 O(n) 시간 복잡도로 빠르게 문제를 해결할 수 있다는 장점이 있습니다.