두 개의 소문자 문자열 s와 t가 주어졌다고 가정해 보겠습니다. 여기서 수행할 수 있는 연산은, 문자열 s에 등장하는 특정 문자의 모든 위치를 다른 문자로 한꺼번에 바꾸는 것입니다. 이 연산은 원하는 만큼 몇 번이든 반복할 수 있으며, 우리는 이 과정을 거쳐 s를 t로 변환할 수 있는지 판별해야 합니다.
예를 들어 입력이 s = "eye", t = "pip"라고 해보겠습니다. 이 경우 출력은 True가 됩니다. 문자 'e'가 등장하는 모든 자리를 'p'로 바꾼 뒤, 'y'를 'i'로 바꾸면 "pip"를 얻을 수 있기 때문입니다.
문제 해결 접근 방식
핵심 아이디어는 간단합니다. s의 각 문자는 변환 과정에서 항상 동일한 문자로만 대응되어야 한다는 점입니다. 즉, s의 문자와 t의 문자 사이에 일관된 매핑 관계가 성립하는지 확인하면 됩니다. 이를 위해 다음 단계를 따릅니다.
s의 문자와 t의 문자 대응 관계를 저장할 맵 m1을 정의합니다.
n := s의 길이로 설정합니다.
i := 0으로 초기화하고, i < n을 만족하는 동안 i를 1씩 증가시키며 아래를 반복합니다.
s[i]가 m1에 이미 존재하는 경우
m1[s[i]]의 값이 t[i]와 같다면 대응 관계에 모순이 없으므로 다음 반복으로 넘어갑니다.
같지 않다면 동일한 문자가 서로 다른 두 문자로 바뀌어야 하는 상황이므로 false를 반환합니다.
s[i]가 m1에 없는 경우
m1[s[i]] := t[i]로 새로운 대응 관계를 등록합니다.
모든 문자를 검사한 후에는 true를 반환합니다.
C++ 구현 예시
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
bool solve(string s, string t) {
map<char, char> m1;
int n = s.size();
for (int i = 0; i < n; i++) {
if (m1.count(s[i])) {
if (m1[s[i]] == t[i]) continue;
return false;
}
else {
m1[s[i]] = t[i];
}
}
return true;
}
int main() {
string s = "eye", t = "pip";
cout << solve(s, t);
}
실행 결과
입력
"eye","pip"
출력
1
출력값 1은 bool 타입의 true가 정수 형태로 출력된 것으로, "eye"를 "pip"로 변환할 수 있음을 의미합니다.
복잡도 분석
시간 복잡도: 문자열의 각 문자를 한 번씩 확인하고, 맵 연산에 O(log k)(k는 서로 다른 문자 수)가 소요되므로 전체 O(n log n)입니다. unordered_map을 사용하면 평균 O(n)으로 개선할 수 있습니다.
공간 복잡도: 등장하는 서로 다른 문자 수만큼 저장 공간이 필요하므로 O(k)이며, 영문 소문자 기준 최대 26입니다.