문제
https://www.acmicpc.net/problem/13413
풀이
백트래킹 (메모리 초과)
백트래킹으로 모든 경우의 수를 구하고 그 중에서 최소 변경 (순서 또는 말 뒤집기) 횟수를 찾기 위해 재귀 호출을 이용했는데, N이 최대 10만이어서 메모리 초과가 발생한다.
초기 상태 문자열의 첫번째 인덱스부터 n까지 늘려가면서 목표 상태 문자열의 문자와 하나씩 비교하고, 서로 다르면 순서를 변경하거나 말을 뒤집는다.
따라서 초기 상태와 목표 상태의 문자열이 모두 다른 최악의 경우, 시간 복잡도는 2^N이 될 것이다...! 재귀 호출이기 때문에 그에 따라 공간 복잡도도 늘어나서 메모리 초과가 발생한 거 같다.
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 100005;
int t, n;
string src, dst;
int ans = MAX;
void dfs(int idx, int cnt, string src){
if(idx == n){
if(src == dst){
ans = min(ans, cnt);
return;
}
return;
}
if(src[idx] != dst[idx]){
string st1 = src;
// 문자 뒤집기
if(st1[idx] == 'B'){
st1[idx] = 'W';
}else{
st1[idx] = 'B';
}
dfs(idx + 1, cnt + 1, st1);
// 문자 순서 변경
string st2 = src;
auto j = src.find(dst[idx], idx + 1);
if(j != string::npos){
swap(st2[j], st2[idx]);
dfs(idx + 1, cnt + 1, st2);
}
}else{
dfs(idx + 1, cnt, src);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--){
cin >> n; // 최대 10만
cin >> src >> dst;
dfs(0, 0, src);
cout << ans << "\n";
ans = MAX;
}
return 0;
}그리디
직관적으로 생각해봤을 때, 각 문자를 뒤집는 것보다 두 문자의 순서를 변경하는 게 횟수를 최소화 할 수 있는 길이다.
ex) BW, WB -> 각 문자를 뒤집으면 2번이지만, 두 문자의 순서를 바꾸면 1번으로 끝이다!
그래서 특정 인덱스의 초기 상태, 목표 상태의 문자가 서로 다를 때, 문자의 순서를 바꾸는 경우를 최대화 시켜야 한다.
이를 위해 다음과 같은 경우를 먼저 찾고! a, b 상태의 문자를 서로 swap 함으로써 초기 상태가 목표 상태에 가까워지게 할 수 있다.
- a: 초기 상태 B, 목표 상태 W
- b: 초기 상태 W, 목표 상태 B
그리고 a 상태가 4개, b 상태가 2개라고 하면, 2개까지는 먼저 스왑해주고 나머지 2개는 각 문자를 뒤집으면 된다.
따라서, a 상태와 b 상태의 개수 중에 최댓값이 곧 우리가 구하고자 하는 답이 된다.
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n; // 최대 10만
string src, dst;
cin >> src >> dst;
int diff[] = {0, 0};
for(int i = 0; i < n; i++){
char a = src[i];
char b = dst[i];
if(a != b){
if(a == 'W') diff[0]++;
else diff[1]++;
}
}
cout << max(diff[0], diff[1]) << "\n";
}
return 0;
}시간복잡도는 O(N)이 된다! 그리디 문제는.. 이 방법으로 최적해를 보장할 수 있는지 정당성을 분석하는 게 중요한 거 같다. 이 문제에서는 확실하게 각 문자를 뒤집는 것보다 두 문자의 순서를 바꾸는 것이 효율적이기 때문에 그리디로 해결할 수 있었다. 문자 하나씩 비교하면서 모든 경우의 수를 다 구하는 것보다 확실히 효율적이다!
최대/최소를 구하는 최적화 문제이면서 입력 크기가 큰 경우에는 효율성까지 고려해야 한다. 따라서 완탐보다는 그리디, DP 같은 방법으로 해결할 수 있는지 더 고민해봐야겠다.
그리고 문제 상황에 따라 누적합, 투포인터, 슬라이딩 윈도우, 이분탐색, 해시, 맵 등을 이용하여 시간 복잡도를 줄일 수 있는지도 고민해보자!
