(2024-11-04) 2 문제 : 백준 - 25381 (ABBC)

 

이 문제는 알고리즘 문제라기보다 아이디어 문제라서 다소 어렵게 느껴질 수도 있다.

 

이 문제의 규칙은 A가 B를 지우고, B가 C를 지우는 것이지만 A가 B를 지우고, C가 B를 지운다고 생각할 수도 있다.

즉, 두 시행 모두 B를 지우므로 B를 가능한 많이 지울 수 있는 경우의 수가 정답이 될 것이다.

 

방법은 여러가지가 있겠지만 본인은 두 번의 과정을 통해 문제를 해결하였다.

 

1. 앞에서부터 C를 탐색하고 C의 앞에 있는 B 중 가장 앞에 있는 B와 C를 제거한다. (만약 앞에 B가 없다면 continue)

2. 뒤에서부터 A를 탐색하고 A의 뒤에 있는 B중 가장 뒤에 있는 B와 A를 제거한다. (만약 뒤에 A가 없다면 continue)

#include <iostream>
#include <vector>

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

int main()
{
    Init();
    std::string Input;
    std::cin >> Input;

    int Answer = 0;
    int BPointer = -1;

    for (int i = 0; i < Input.size(); i++)
    {
        if (Input[i] == 'B' && BPointer == -1)
        {
            BPointer = i;
        }
        else if (Input[i] == 'C' && BPointer != -1)
        {
            if (BPointer < i)
            {
                Input[i] = 'X';
                Input[BPointer] = 'X';

                while (BPointer < Input.size() && Input[BPointer] != 'B')
                {
                    BPointer++;
                }

                Answer++;
            }
        }
    }

    BPointer = -1;

    for (int i = Input.size() - 1; i >= 0; i--)
    {
        if (Input[i] == 'B' && BPointer == -1)
        {
            BPointer = i;
        }
        else if (Input[i] == 'A' && BPointer != -1)
        {
            if (BPointer > i)
            {
                Input[i] = 'X';
                Input[BPointer] = 'X';

                while (BPointer >= 0 && Input[BPointer] != 'B')
                {
                    BPointer--;
                }

                Answer++;
            }
        }
    }

    std::cout << Answer;

    return 0;
}