문제 이해 단계
https://www.acmicpc.net/problem/13019
13019번: A를 B로
첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다.
www.acmicpc.net
대문자 알파벳으로 이루어진 문자열 A와 B가 입력으로 들어온다.
문자열 A를 B로 바꾸는 것이 목표.
할 수 있는 연산은 알파벳 하나를 골라 가장 앞으로 보내는 것이다.
이때 최소 몇 번 만에 만들 수 있는지 구하는 문제
문제 접근 단계
일단 입력으로 들어오는 문자열의 길이가 50이 넘지 않는다.
따라서 시간초과는 크게 신경 쓰지 않아도 될 것 같다.
연산에서 중간에 있는 문자를 골라도 상관이 없다.
하지만 무조건 가장 앞으로 보내야 하기 때문에,
골랐던 문자 앞에 있던 문자들은 한 칸씩 뒤로 밀리게 된다.
반대로 말하면 골랐던 문자 뒤에 있던 문자들의 위치는 변하지 않는다는 소리이다.
그렇기 때문에 뒤에 있는 문자부터 탐색하여 고정하는 것이 직관적이다.
아래와 같이 이미 단어가 동일한 경우에는, 없는 셈 치고 탐색 범위에서 제외해도 된다.
왜냐면 어차피 해당 문자는 움직이지도 않고, 선택될 일도 없기 때문이다.
여기서 C는 왜 포함되지 않을까?
끝에 있지 않기 때문이다.
문자열 A( ACBD )에서 B가 맨 앞으로 움직이면서 위치가 변한다.
때문에 고정된 위치가 아니라는 근거로 포함되지 않는다.
포함되기 위해서는 아래와 같이 연속된 경우여야 한다.
위의 경우를 제외하곤 끝에서부터 탐색을 하며 맨 앞으로 하나씩 넘겨야 한다.
근데 어떤 걸 어느 순서로 넘겨야 하나?
사실 이걸 고민할 필요는 없다.
우리가 구해야 하는 것은 최소의 횟수가 때문에 맨 앞으로 넘긴 후,
밀린 자리의 알파벳들이 같은지 판단해주기만 하면 된다.
왜냐하면 최소의 횟수를 구하는 것이기 때문에
모든 매칭이 한 번만에 일어난다고 가정하면 되기 때문이다.
무슨 말이냐면 아래와 같다.
원래대로 끝에서부터 탐색하여 두 문자가 맞지 않으면 앞으로 넘기면 BCA가 된다.
그럼 CBA와 맞지 않아, 한번 더 연산을 해서 총 연산 횟수가 3이 된다.
하지만 우리는 B를 먼저 넘기고 C를 그다음 넘기는 것이 최소 횟수인 것을 알고 있다.
그렇기 때문에 우리는 모든 매칭이 한 번만에 일어난다고 가정하고, 넘기는 것에만 집중하는 것이다.
ABC에서 C를 넘기면 AB가 남는다.
그리고 B와 A를 비교하고 맞지 않으므로 B를 넘긴다.
마지막으로 남은 A와 A가 맞으므로 그다음 B 문자열은 CBA에서 B로 넘어간다.
그런데 이미 문자열 A의 ABC는 모두 탐색했으므로 작업을 종료한다.
넘긴 B와 C는 최소 연산임을 가정했으므로 B 문자열의 CB와 알아서 매칭됐다고 가정한다.
그러므로 총 2번을 넘겼으니 답이 2가 되는 것이다.
요약하자면 두 문자열을 맨 뒤에서부터 비교하여,
1.
두 문자가 일치하면 버리고, 일치하지 않으면 문자열 A의 문자는 넘긴다.
이를 문자열 A의 문자가 일치할 때까지 반복한다.
(문자열 A의 인덱스 0까지만)
이때 넘기는 것을 반복하므로
연산 횟수를 +1씩 계속한다.
2.
일치하면 문자열 B의 인덱스- 1 하고,
같은 과정을 문자열 A의 인덱스가 0까지 갈 때까지 반복한다.
이를 이제 문제 구현 단계에서 코드로 구현하면 된다.
문제 구현 단계
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string A,B;
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> A >> B;
int idx = B.length()-1; // 문자열 B의 인덱스
int ans = 0; // 연산 횟수
// 문자열 A의 인덱스는 계속해서 끝에서부터 탐색
for(int i = A.length()-1; i >= 0; i--){
if(A[i] == B[idx]) idx--; // 두 문자가 같으면 문자열 B 인덱스 낮춤
else ans++; // 다르면 앞으로 보내는 작용(문자열 B 인덱스 가만히 있음)
}
// 두 문자열이 같은지 체크하여 만들 수 있는 문자열인지 확인
sort(A.begin(),A.end());
sort(B.begin(),B.end());
if(A.compare(B) == 0) cout << ans;
else cout << "-1";
}위에서 설명한 것이다.
문자열 B 인덱스는 idx로 정의했다.
문자열 A 인덱스는 어차피 멈추지 않고 끝에서부터 인덱스 0까지 계속해서 탐색한다.
두 문자가 같으면 문자열 B 인덱스를 -1 해서다음에 비교할 문자로 넘긴다.
그렇지 않으면 문자열 A의 문자만 넘겨서 마치 문자가 앞으로 넘어간 작용을 해준다.
가장 밑에 두 문자열을 정렬해 주고 비교해 준 것은
두 문자열이 같은지 확인함으로써, 만들 수 있는 문자열인지를 체크해 주기 위함이다.
풀이는 여기까지이다.
시행착오
풀이를 보고서도 살짝 모르겠다. 저게 최소가 된다라는 증명은 잘 못하겠다.
인터넷을 보고서 알았는데, 저게 왜 최소일까? 무조건 한 번만이 왜 되지?
내가 멍청한 건가 모르겠네..
어렴풋이 이해가 되긴 하는데..
뭔가 아직까지 꺼림칙하고 찝찝하다.
생활비..