백준 13019 - A를 B로

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

풀이

일단 서로 가지고 있는 문자가 다르면 문제에 제시된 연산으로 같게 만드는 것이 불가능하므로 -1을 출력한다.

 

위 조건을 통과하면 답의 초기값을 0으로 설정하고 B의 맨 뒤와 A의 맨 뒤에 포인터(index)를 둬서 서로 비교한다. 둘이 같지 않으면 A의 마지막을 맨 앞으로 보내야 하는 것은 자명하므로 앞으로 보냈다 치고 답을 1 증가시킨다.

 

두 포인터가 같다면 B의 포인터는 더 볼 의미가 없으므로 B의 포인터에 1을 뺀다.

 

A는 뭐가 되었든 1을 빼면서 모든 문자를 순회한다.

 

이렇게 A를 순회하면서 증가시킨 값들이 최종 답이다.

뭐?

도대체 무슨 소리를 하고 있는 건지 이해하지 못할 수 있다. 예제 케이스 1번을 보자.

 

위 방법대로 맞지 않는 문자를 앞으로 보낸다 했을 때 맞지 않은 문자를 만난 순서대로 바로 보내는 것이 아니라 보낼 순서를 잘 정해서 보내면 아무튼 B랑 같은 배열이 되도록 할 수 있다.

 

증명은 하지 못했다. 이에 관한 증명을 알고 있으면 댓글로 제보를 남겨주면 감사할 것 같다.

 

위 논리 통해 아무튼 맞게 보낼 수 있으므로 위 방식대로 맞지 않은 개수만 세어주면 된다.

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
int cnt1[140], cnt2[140];
 
void solve()
{
  string s1, s2;
  cin >> s1 >> s2;
 
  for (char &i : s1)
  {
    cnt1[i]++;
  }
  for (char &i : s2)
  {
    cnt2[i]++;
  }
 
  for (char i = 'A'; i <= 'Z'; i++)
  {
    if (cnt1[i] != cnt2[i])
    {
      cout << -1;
      return;
    }
  }
 
  int ans = 0;
  int idx = s1.size() - 1;
  for (int i = (int)s1.size() - 1; i >= 0; i--)
  {
    if (s1[i] != s2[idx])
      ++ans;
    else
      --idx;
  }
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
 
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록