[백준] 12904번 A와B - C++

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

12904번: A와 B

문제

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. 

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

---

이 문제 풀이의 가장 중요한 개념은 S -> T 로 가는 것이 아닌 T -> S로 가는 것이다.

S -> T 로 가려하면 2가지 선택지가 있지만 T -> S로 가려면 뒤에 A 가 있으면 제거하고 B 가 있으면 제거를 한 뒤 문자열을 뒤집으면 된다.

첫 번째 풀이는 문자열 라이브러리를 사용하지 않고 문자열이 시작되는 위치와 끝나는 위치를 저장해 두고 현재 문자열의 방향에 따라 front 나 back의 위치에 있는 원소를 삭제한다. 삭제한 원소가 B 라면 dir을 바꿔준다.

두 번째 풀이는 B를 만나면 실제로 문자열을 뒤집는 것이다.

#include <iostream>

using namespace std;

int main(){
    string s;
    string t;
    string ans;
    int tlen, slen, front, back;
    bool dir = false;
    
    cin >> s >> t;
    slen = s.length();
    back = t.length() - 1;
    front = 0;
    while(back - front  + 1 > slen){
        char cur;
        if(dir == false)
            cur = t[back--];
        else
            cur = t[front++];
        if(cur == 'B')
            dir = !dir;
    }
    ans = "";
    if(dir == false){
        for(int i = front; i <= back; i++)
            ans += t[i];
    }
    else{
        for(int i = back ; i >= front; i--)
            ans += t[i];
    }
    if(ans == s)
        cout << 1;
    else
        cout << 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    string s;
    string t;
    
    cin >> s >> t;
    while(s.length() != t.length()){
        bool flag = false;
        if(t[t.length() - 1] == 'B')
            flag = true;
        t.erase(t.end()-1);
        if(flag)
            reverse(t.begin(),t.end());       
    }
    if(s == t)
        cout << 1;
    else
        cout << 0;
}

---

  문자열을 뒤집는 과정이 복잡할 것 같아 front와 back 변수를 두어 문자열을 판단하려고 하였지만 문자열을 뒤집어주는 편리한 라이브러리가 있었다. 이번에도 충분한 고민을 거쳐 문제를 푸니 코드 작성을 완료하면 바로 답이 나오는 것 같다. 확실히 골드 5 수준의 문제는 아이디어만 있으면 실제 코드 작성은 길지 않은 것 같다!

  그래도 요즘에는 문제가 조금 잘 풀리는 것 같아 다행이다. 앞으로도 꾸준히 열심히 해야겠다!!