백준 13019 A를 B로 (C++)

https://www.acmicpc.net/problem/13019

#include <iostream>
#include <vector>

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s;
    string e;

    cin >> s;
    cin >> e;

    vector<int> scnt(26, 0);
    vector<int> ecnt(26, 0);

    for (int i = 0; i < s.size(); i++) {
        scnt[s[i] - 'A']++;
        ecnt[e[i] - 'A']++;
    }

    for (int i = 0; i < 26; i++) {
        if (scnt[i] != ecnt[i]) {
            cout << -1;
            return 0;
        }
    }

    int ans = 0;
    int eidx = e.size() - 1;

    for (int i = s.size()-1; i >= 0; i--) {
        if (s[i] == e[eidx]) {
            eidx--;
        } else ans++;
    }

    cout << ans;


    return 0;
}

1. 문제

두 문자열 a, b가 주어진다. a를 b로 바꿀 건데, a의 한 글자를 골라 문자열의 맨 앞으로 옮기는 연산으로 옮길 것이다. 이 때 필요한 연산 최소 횟수를 출력하라. 단. a를 b로 바꿀 수 없을 경우 -1을 출력한다.

2. 풀이

문자를 앞으로 보내는 연산을 하여 앞의 문자는 연산을 할 때마다 배열이 바뀌기 때문에 맨 뒤에서 부터 문자를 탐색한다.

    for (int i = 0; i < s.size(); i++) {
        scnt[s[i] - 'A']++;
        ecnt[e[i] - 'A']++;
    }

    for (int i = 0; i < 26; i++) {
        if (scnt[i] != ecnt[i]) {
            cout << -1;
            return 0;
        }
    }

우선 문자열에 있는 각 문자의 개수를 세어준다. 두 문자열에 대해 각 문자의 개수가 다르다면 a에서 b를 만들 수 없으므로 -1을 출력한다.

    int ans = 0;
    int eidx = e.size() - 1;

    for (int i = s.size()-1; i >= 0; i--) {
        if (s[i] == e[eidx]) {
            eidx--;
        } else ans++;
    }

각 문자열의 맨 뒤에서부터 문자열을 하나씩 탐색한다. 만약 문자열이 같다면 두 포인터를 앞으로 옮겨 다음 연산을 준비한다. 그렇지 않다면 연산 수행 횟수를 증가시킨다. 연산을 했으므로 s[i]는 맨 앞으로 옮기게 된다. 따라서 i만 감소시킨다. 

예제 5의 케이스이다. 2번 idx에서 A와 C가 일치하지 않으므로 A를 대상으로 연산을 진행하면 i만 감소시키고 그 다음 i와 eidx를 비교하는 것을 볼 수 있다.

 

연산이 끝나고 ans를 출력하면 정답을 구할 수 있다.