백준 12904 - A와 B (C++)

 

 

문자열 2개가 주어진다. 첫 번째로 주어진 문자열을 특정 규칙에 의해 변환했을 때, 두 번째로 주어진 문자열을 만들 수 있는가를 찾으면 되는 문제이다.

 

규칙은 2가지이다.

1. 문자열의 끝에 A를 삽입한다.

2. 문자열을 뒤집은 뒤, 끝에 B를 삽입한다.

 

A가 주어졌다면, AA를 만들 수도 있고 AB를 만들 수도 있다.

AA는 AAA가 될 수도 있고, AAB가 될 수도 있다.

AB또한 BAB가 될 수도 있고, ABA가 될 수도 있다.

 

이렇게 여러가지 경우의 수 중에 ABBA가 될 수 있는 경우의 수가 있다면,  1을 출력하고 없다면 0을 출력하면 된다.

 

문제 풀이

 

해당 문제는 시간 복잡도를 줄이는 것이 핵심인 것 같다. 주어진 두개의 규칙에 대해 모든 경우의 수를 구하면서 확인해나갈 수도 있겠지만, 최악의 경우엔 2^1000만큼의 경우를 확인해야 한다. (2초안에 계산되기란 사실상 불가능이다.)

 

또한, 문자열을 직접 뒤집는 연산이나 문자열을 비교하는 연산도 가벼운 연산이 아니기 때문에 모든 경우를 계속 비교하는 것은 말이 안된다.

 

그래서 본인은 몇가지 최적화를 진행하였다.

 

1. 문자열을 직접 뒤집지 않는다. 

문자열이 현재 뒤집어진 상태인지 아닌지를 기록하는 bool값을 두고 문자열을 다루었다.

문자열을 뒤집고 뒤에다가 B를 추가한다는 뜻은 기존의 문자열 맨 앞에 B를 추가한다음 뒤집는 것과 같다.

즉, 현재 문자열을 계속 뒤집는 것이 아니라 문자열이 뒤집어진 상태인지 아닌지만 체크하여 B를 앞에다가 추가할 지, 뒤에다가 추가할 지에 대한 것만 확인해주었다.

이후, 문자열을 직접 비교할 필요가 있을 때엔, bool값에 따라 문자열을 뒤집어 비교하도록 하였다.

이로 인해, 문자열을 뒤집는 행위는 비교하는 순간에만 진행하게 된다.

 

2. 문자열의 비교는 size가 동일할 때만 해주었다.

문자열의 길이가 다르면 애초에 비교할 가치가 없다. size가 같을 때에만 문자열 비교를 해주었다.

 

3. 시작 문자열로부터 분기를 나눠가며 경우를 탐색한 것이 아니라, 결과 문자열로부터 역추적하며 시작 문자열이 될 수 있는가를 탐색하였다.

시작 문자열로부터 출발하여 경우를 세면, 너무 많은 경우를 탐색해야 한다.

하지만, 결과 문자열로부터 백트래킹을 하게 되면 지나왔던 길만 되돌아가는 것이기 때문에 문자열의 길이만큼의 연산만 진행해주면 된다.

 

4. 문자열을 직접 제거하지 않고, 투포인터 형식을 사용하였다.

백트래킹을 하게 되면, 문자를 제거해주어야 하는데 문자열도 일종의 배열이기 때문에 제거 연산의 시작복잡도가 O(n)이다. 그렇기 때문에 직접 문자를 제거하지 않고 Left와 Right 두개의 변수를 통해 남아있는 문자열의 인덱스만 갱신할 것이다.

 

아래 과정을 보며, 이해해보자.

 

isFlip은 처음에 false로 두고 시작해보자.

목표 문자열에서 가장 마지막으로 문자가 추가된 곳은 당연히 가장 마지막일 것이다.

그러므로 마지막부터 제거를 해보자.

 

마지막 문자를 제거한 뒤, Right를 앞으로 당겨서 남아있는 문자의 인덱스를 표시해주었다.

다시 뒤의 문자를 제거해보자. 

이번엔, 제거한 문자가 B였다. B는 추가할 때 문자열을 뒤집어야 하기 때문에, 문자를 제거하며 역추적할 때에도 뒤집어주어야 한다. 그러므로 isFlip을 true로 만들어주었다.

 

이젠, isFlip이 true이므로 문자를 앞에서부터 제거해야 한다.

이렇게 제거해주었다. 남아있는 목표 문자열의 길이가 시작 문자열과 동일하기 때문에, 문자열 비교를 해주자.

두 문자열이 같으므로, 시작 문자열은 목표 문자열이 될 수 있다.

 

다음 경우도 보자.

 

이번에도, 뒤에서부터 제거해보자.

뒤의 문자를 제거해주었고, B를 제거했기 때문에 문자를 isFlip을 true로 만들어주었다.

목표 문자열과 시작 문자열의 길이가 같아졌으므로 두 문자를 비교해보자.

현재, isFlip이 true이므로 문자열을 뒤집어서 비교해야 한다.

 

시작 문자열이나 목표 문자열이나 아무거나 뒤집어도 되지만, 본인은 시작 문자열을 뒤집어주었다.

 

시작 문자열 : BA

목표 문자열 : AB

 

서로 다르기 때문에, 시작 문자열은 목표 문자열에 도달할 수 없음을 알 수 있다.

 

코드 풀이

 

std::string StartStr;
std::cin >> StartStr;

std::string FlipStr;
FlipStr.resize(StartStr.size());

for (int i = 0; i < StartStr.size(); i++)
{
    FlipStr[i] = StartStr[StartStr.size() - i - 1];
}

std::string TargetStr;
std::cin >> TargetStr;

 

먼저, 시작 문자열을 입력받았고, 나중에 뒤집은 문자열을 비교할 것이기 때문에, 미리 뒤집은 문자열을 저장해주었다.

이후, 목표 문자열도 입력을 받아주었다.

 

bool isFlip = false;

int Left = 0;
int Right = TargetStr.size() - 1;

 

문자열이 뒤집어진 상태인지를 표현하는 isFlip과 인덱스를 나타내기 위한 left와 Right도 선언해주었다.

 

while (Left <= Right)
{
    if (Right - Left + 1 == StartStr.size())
    {
        std::string CurStr = TargetStr.substr(Left, Right - Left + 1);

        if (isFlip == true && CurStr == FlipStr)
        {
            std::cout << 1;
            break;
        }    
        else if (isFlip == false && CurStr == StartStr)
        {
            std::cout << 1;
            break;
        }
        else
        {
            std::cout << 0;
            break;
        }
    }

    if (isFlip == false)
    {
        if (TargetStr[Right] == 'A')
        {
            TargetStr[Right] = 'X';
            Right--;
        }
        else
        {
            isFlip = true;
            TargetStr[Right] = 'X';
            Right--;
        }
    }
    else
    {
        if (TargetStr[Left] == 'A')
        {
            TargetStr[Left] = 'X';
            Left++;
        }
        else
        {
            isFlip = false;
            TargetStr[Left] = 'X';
            Left++;
        }
    }
}

 

먼저, 남아있는 문자열의 길이가 시작 문자열과 같은지 검사해주고 있다.

길이가 같다면, 남아있는 문자열과 시작 문자열을 비교해주었으며, 같은 경우에는 1을 출력해주었고 다른 경우에는 0을 출력해주었다.

 

두 문자열의 길이가 다르다면, 문자 제거 연산을 실행해주었다.

현재, isFlip이 false라면 맨 뒤의 문자를 제거하였고, true라면 맨 앞의 문자를 제거해주었다.

또한, 제거할 문자가 B라면 isFlip을 반대로 뒤집어 주었다.

 

이렇게 간단하게 답을 도출할 수 있다.

 

코드 전문

#include <iostream>
#include <vector>
#include <string>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    std::string StartStr;
    std::cin >> StartStr;

    std::string FlipStr;
    FlipStr.resize(StartStr.size());

    for (int i = 0; i < StartStr.size(); i++)
    {
        FlipStr[i] = StartStr[StartStr.size() - i - 1];
    }

    std::string TargetStr;
    std::cin >> TargetStr;

    bool isFlip = false;

    int Left = 0;
    int Right = TargetStr.size() - 1;

    while (Left <= Right)
    {
        if (Right - Left + 1 == StartStr.size())
        {
            std::string CurStr = TargetStr.substr(Left, Right - Left + 1);

            if (isFlip == true && CurStr == FlipStr)
            {
                std::cout << 1;
                break;
            }
            else if (isFlip == false && CurStr == StartStr)
            {
                std::cout << 1;
                break;
            }
            else
            {
                std::cout << 0;
                break;
            }
        }

        if (isFlip == false)
        {
            if (TargetStr[Right] == 'A')
            {
                TargetStr[Right] = 'X';
                Right--;
            }
            else
            {
                isFlip = true;
                TargetStr[Right] = 'X';
                Right--;
            }
        }
        else
        {
            if (TargetStr[Left] == 'A')
            {
                TargetStr[Left] = 'X';
                Left++;
            }
            else
            {
                isFlip = false;
                TargetStr[Left] = 'X';
                Left++;
            }
        }
    }

    return 0;
}