백준 - 12904 A와 B

[Gold V] A와 B - 12904

문제 링크

성능 요약

재귀 + unordred map 사용 => 메모리: 3612 KB, 시간: 0 ms
반복문 => 메모리: 2024 KB, 시간: 0 ms

분류

그리디 알고리즘, 구현, 문자열

제출 일자

2024년 4월 4일 21:30:07

문제 설명

수빈이는 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를 만드는 것으로 풀었는데 시간초과가 발생했다. 그래서 unordred map으로 visit 처리를 해줬는데 이번에는 메모리초과가 발생했다.

메인 아이디어

뒤집어서 생각하여 긴 문자열로부터 짧은 문자열을 만들면 된다.
짧은 문자열에서 긴 문자열을 만드는 것보다, 긴 문자열에서 짧은 문자열을 만드는 것의 경우의 수가 더 적기 때문이다.

뒤에서 A를 빼기

문자열의 마지막 문자가 A라면 A를 뺀다.

뒤에서 B를 빼고 뒤집기

s->t를 만들 때 가능한 연산은 뒤집은 후 B를 더해주는 것이고,
이를 반대로 하면 뒤에서 B를 빼고 뒤집는 것이다.

코드

재귀 + unordred map

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <string>
using namespace std;
string s, t;
bool flag;
int ss, sa, sb, ta, tb;
unordered_map<string, bool> m;

void solve(string str, int cura, int curb) {
    if (flag || (m.find(str) != m.end())) return;
    if (str == s) {
        flag = 1;
        return;
    }
    m[str] = 1;
    if (cura > sa && str[str.size() - 1] == 'A') 
        solve(str.substr(0, str.size() - 1), cura - 1, curb);
    if (curb > sb && str[str.size() - 1] == 'B') {
        string tmp = str.substr(0, str.size() - 1);
        reverse(tmp.begin(), tmp.end());
        solve(tmp, cura, curb - 1);
    }
}
int main(void) {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> s >> t;
    ss = s.size();
    for (auto x : s) {
        if (x == 'A') sa++;
        else if (x == 'B') sb++;
    }
    for (auto x : t) {
        if (x == 'A') ta++;
        else if (x == 'B') tb++;
    }
    solve(t, ta, tb);
    cout << flag;
}

반복문

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s, t;
int main(void) {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> s >> t;
    while (1) {
        if (t.back() == 'A') 
            t.pop_back();
        else if (t.back() == 'B') {
            t.pop_back();
            reverse(t.begin(), t.end());
        }
        if (t.size() == s.size()) {
            cout << (t == s ? 1 : 0);
            return 0;
        }
    }
}