[Algorithm] Baekjoon 12904번 : A와 B

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

12904번: A와 B

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    bool isReversedDirection = false; 
    deque<char> dq;
    string start;
    string target;
    int startSize = 0;
 
    cin >> start >> target;
    
    for (int i = 0; i < target.size(); ++i)
    {
        dq.push_back(target[i]);
    }
    startSize = start.size();
 
    while (1)
    {
        if (!isReversedDirection)
        {
            if (dq.back() == 'A')
            {
                dq.pop_back();
            }
            else
            {
                dq.pop_back();
                isReversedDirection = !isReversedDirection;
            }
        }
        else
        {
            if (dq.front() == 'A')
            {
                dq.pop_front();
            }
            else
            {
                dq.pop_front();
                isReversedDirection = !isReversedDirection;
            }
        }
 
        if (dq.size() == startSize)
        {
            break;
        }
    }
 
    if (!isReversedDirection)
    {
        for (int i = 0; i < startSize; ++i)
        {
            if (start[i] != dq[i])
            {
                cout << 0;
                return 0;
            }
        }
    }
    else
    {
        for (int i = 0; i < startSize; ++i)
        {
            if (start[i] != dq[startSize - i - 1])
            {
                cout << 0;
                return 0;
            }
        }
    }
 
    cout << 1;
}

 

문제의 조건에 '추가'만 있을 뿐, '삭제'가 없기에 빠른속도내로 풀 수 있는문제.

그냥 얼추보면은 완전탐색마냥 풀어야 할 것 같지만, 삭제가 없기 때문에 target에서 연산을 역으로 적용하다가 크기가 start랑 같을 떄 비교해서 가능여부를 판단하면 된다. 사실상 루트가 한개다.

 

문제의 연산에는 뒤집는다...라는 동작이 있지만, reverse라는 동작자체가 O(n)이기 때문에, 보통 실제로 뒤집지는 않고 뒤집은것'처럼' 구현하는 경우가 많다. 따로 bool변수를 선언해서 현재 정방향인지 역방향인지를 표시해주면 된다.

역방향일 경우 문자열의 뒤에서 문자를 빼는게 아니라 앞에서 빼고, 정방향이면 뒤에서 문자를 빼주면 된다.