문제 이해하기
두 개의 문자열 s와 t가 주어졌을 때, 이 두 문자열이 서로 '가까운(close)' 관계인지 확인하는 프로그램을 작성해 보겠습니다. 두 문자열이 가깝다고 판단하려면, 아래 두 가지 연산만으로 한 문자열을 다른 문자열로 변환할 수 있어야 합니다.
문자열 내에 이미 존재하는 임의의 두 문자를 서로 맞바꿉니다. (예: abcde → aecdb)
한 문자의 모든 등장 위치를 다른 기존 문자로 일괄 변경하고, 그 반대도 동시에 적용합니다. (예: aacabb → bbcbaa — 모든 a는 b로, 모든 b는 a로 변환)
이 연산들은 어느 문자열에든 원하는 만큼 자유롭게 반복해서 적용할 수 있습니다.
예시 확인
예를 들어 입력이 s = "zxyyyx", t = "xyyzzz"라고 해보겠습니다. 이 경우 출력은 True입니다. 세 번의 연산만으로 t를 만들어낼 수 있기 때문입니다.
"zxyyyx" → "zxxyyy" (문자 교환)
"zxxyyy" → "yxxzzz" (문자 치환)
"yxxzzz" → "xyyzzz" (문자 교환)
핵심 아이디어
위 두 연산의 성질을 잘 살펴보면 중요한 사실을 알 수 있습니다. 문자 교환은 어떤 문자의 종류나 빈도도 바꾸지 않고 순서만 변경하며, 전체 치환은 문자 종류를 재배치할 뿐 빈도 분포 자체는 그대로 유지합니다. 따라서 두 문자열이 가깝기 위한 필요충분조건은 다음과 같습니다.
두 문자열이 사용하는 문자의 집합이 완전히 동일해야 합니다.
각 문자의 등장 횟수 목록(빈도 분포)이 정렬했을 때 동일해야 합니다.
풀이 접근 방법
s와 t가 공통되지 않은 문자를 하나라도 포함한다면 False를 반환합니다.
a := s에 있는 문자들의 빈도 값 목록
b := t에 있는 문자들의 빈도 값 목록
목록 a와 b를 각각 정렬합니다.
정렬 후 a와 b가 같지 않다면 False를 반환합니다.
모든 조건을 통과했다면 True를 반환합니다.
구현 예제
아래 코드를 통해 더 명확하게 이해할 수 있습니다.
from collections import Counter
def solve(s, t):
if set(s) != set(t):
return False
a = list(Counter(s).values())
b = list(Counter(t).values())
a.sort()
b.sort()
if a != b:
return False
return True
s = "zxyyyx"
t = "xyyzzz"
print(solve(s, t))입력
"zxyyyx", "xyyzzz"
출력
True
정리
이 문제는 Python의 set과 collections.Counter를 활용하면 간결하게 해결됩니다. 시간 복잡도는 문자열 길이를 n이라 할 때 O(n log n)이며, 정렬 단계가 지배적입니다. 문자 집합 비교와 빈도 분포 비교라는 두 단계만 거치면 두 문자열의 '가까움' 여부를 정확히 판별할 수 있습니다.