크기가 같은 두 문자열 s와 t가 있다고 가정해 봅시다. 한 단계(step)마다 t의 임의의 문자 하나를 선택해 다른 문자로 교체할 수 있습니다. 목표는 t를 s의 아나그램(anagram)으로 만들기 위해 필요한 최소 단계 수를 구하는 것입니다.
참고로, 어떤 문자열의 아나그램이란 동일한 문자들로 구성되어 있으면서 순서가 다르거나(또는 같은) 문자열을 의미합니다.
예를 들어 입력이 "yxy"와 "xyx"라면 문자 하나만 교체하면 되므로 결과는 1이 됩니다.
접근 방법
핵심 아이디어는 두 문자열에 공통으로 등장하는 문자의 개수를 세는 것입니다. 전체 길이 n에서 이미 일치하는 문자 수를 빼면, 교체해야 할 문자의 최소 개수를 바로 알 수 있습니다. 구체적인 단계는 다음과 같습니다.
- n := s의 문자 개수
- 맵 m을 만들어 s에 등장하는 각 문자의 빈도수를 저장하고, 맵 m2를 만들어 t에 등장하는 각 문자의 빈도수를 저장합니다.
- ret := n 으로 초기화합니다.
- m의 각 키-값 쌍 it에 대해 다음을 수행합니다.
- x := it의 값과 m2[it의 키] 중 최솟값
- ret에서 x만큼 감소시킵니다.
- ret을 반환합니다.
C++ 구현 예제
다음 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSteps(string s, string t) {
int n = s.size();
map<char, int> m1;
for(int i = 0; i < s.size(); i++){
m1[s[i]]++;
}
int ret = n;
map<char, int> m2;
for(int i = 0; i < t.size(); i++){
m2[t[i]]++;
}
map<char, int>::iterator it = m1.begin();
while(it != m1.end()){
int x = min(it->second, m2[it->first]);
ret -= x;
it++;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.minSteps("yxy", "xyx"));
}입력
"yxy" "xyx"
출력
1
복잡도 분석
std::map을 사용하므로 시간 복잡도는 O(n log n)입니다. unordered_map이나 크기 26의 정수 배열을 사용하면 O(n)까지 개선할 수 있습니다. 공간 복잡도는 서로 다른 문자의 종류 수에 비례하며, 알파벳 소문자만 다룬다면 사실상 O(1)로 볼 수 있습니다.