BOJ 13019 : A를 B로

• 문제 링크 : http://boj.kr/13019
• 난이도 : G4
• 태그 : 그리디, 정렬

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    string a, b;
    cin >> a >> b;
    int n = a.length();
    reverse(all(a));
    reverse(all(b));
    int cnt = 0, idx = 0;
    for(int i = 0; i < n; i++) {
        while(idx < n && b[i] != a[idx]) {
            idx++;
        }
        if(idx == n) break;
        cnt++;
        idx++;
    }
    sort(all(a));
    sort(all(b));
    if(a != b) cout << -1;
    else cout << n - cnt;
    
    return 0;
}

---

풀이

A를 B로 바꿀 때 필요한 최소 횟수를 찾기 위해서는 이동하지 않아도 되는 문자를 확인하면 된다.

 

우선 문자열의 모든 문자가 다르다고 가정하고 생각해보자.

B의 뒤에서부터 문자에 번호를 1부터 순서대로 붙이고, A에도 동일한 문자에 동일한 번호를 붙인다. A의 문자에 붙여진 번호를 수열로 나타낼 수 있다. A = "EBCADF", B = "FEDCBA"라고 했을 때 수열은 {5, 2, 3, 1, 4, 6}이다. 우리는 이 수열이 {6, 5, 4, 3, 2, 1}의 형태가 되어야 함을 알고 있다. 따라서 오른쪽부터 확인하며 넘겨야 하는 것을 정할 수 있다. 연산을 시행하며 따라가보자.

{6 | 5, 2, 3, 1, 4} : 가장 오른쪽이 1이어야 하므로 6은 앞으로 넘겨야 한다.

{4, 6 | 5, 2, 3, 1} : 가장 오른쪽이 1이어야 하므로 4는 앞으로 넘겨야 한다.

{4, 6 | 5, 2, 3 | 1} : 가장 오른쪽이 1이므로 1은 앞으로 넘길 필요가 없다.

{3, 4, 6 | 5, 2 | 1} : 그 다음은 2여야 하므로 3은 앞으로 넘겨야 한다.

{3, 4, 6 | 5 | 2, 1} : 그 다음은 2여야 하므로 2는 앞으로 넘길 필요가 없다.

{3, 4, 5, 6 | X | 2, 1} : 그 다음은 3이어야 하므로 5는 앞으로 넘겨야 한다.

앞으로 넘겨야 하는 수의 순서는 넘기는 순서를 임의로 정할 수 있다. 따라서 넘기는 순서는 중요하지 않다.

위의 과정에서 연산을 시행한 경우는 시행해야 함이 명확하다. 연산을 시행하지 않은 경우 연산을 시행하더라도 나머지 연산에는 영향을 주지 않으므로 앞의 과정이 최적임을 알 수 있다.

 

문자열에 동일한 문자가 여러 개 있어도 같은 문자 C에 대해 앞에서부터 C1, C2, C3 ...로 번호를 매기면 이를 다른 문자로 볼 수 있다. 따라서 문자열의 모든 문자가 다르다고 가정하더라도 일반성을 잃지 않는다.

 

이제 앞에서 수열로 확인한 과정을 문자열 상태로 확인할 수 있다.

 

바꿀 수 없는 경우는 정렬한 뒤 같은지 확인하면 된다.