백준 16120 - PPAP (C++)

 

 

주어진 문자가 PPAP문자열인지 테스트하는 문제이다.

 

PPAP문자열의 규칙은 아래와 같다.

 

1. P는 PPAP문자열이다.

2. PPAP문자열에서 P 하나를 PPAP로 바꾼 것도 PPAP 문자열이다.

Ex) "PPAP"PAP ,  P"PPAP"AP , PPA"PPAP" 

 

어떤 문자열이 주어졌을 때, 해당 문자열이 PPAP인지 아닌지를 검사하면 된다.

문제 풀이

 

어떤 PPAP문자열에서 P를 PPAP로 바꾼 것이 PPAP문자열이라면, 반대로 현재 문자열에서 PPAP를 모두 P로 바꿨을 때, 해당 문자열이 PPAP문자열이라면 현재 문자열도 PPAP문자열이라고 역으로 추론할 수 있다.

 

예를 들어보자.

P -> PPAP -> PPPAPAP 라는 문자열이 있다고 했을 때, PPPAPAP 문자열이 입력으로 주어졌다고 해보자.

이 문자열에서 PPAP를 모두 지워보자.

 

P"PPAP"AP -> PPAP

"PPAP" -> P 

 

즉, PPAP문자열이 맞다면 문자열 내부의 PPAP를 모두 지우면 P가 나올 수 밖에 없다. 모든 PPAP문자열은 P로부터 시작하기 때문이다.

 

반대로 PPAP문자열이 아니라면?
PPAPAAP라는 문자열이 주어졌다고 해보자.

"PPAP"AAP -> PAAP 

PAAP 문자열에는 더이상 PPAP가 없기 때문에 더 제거할 수가 없다.

현재 상태의 문자열이 P가 아니므로, PPAPAAP는 PPAP문자열이 아니라고 추론할 수 있다.

 

그렇다면, PPAP를 어떻게 제거해야 할까?
그냥 std::string을 사용하여 제거하게 되면, 시간초과가 발생할 것이다. 왜냐하면, 문자열은 배열기반이기 때문에 삭제연산이 매우 느리기 때문이다.

 

그렇기 때문에, 이런 유형의 문자열 문제는 대부분 Stack을 사용하여 해결하게 된다.

예를들어 보자.

 

PPPAPAP 를 string을 사용해서 PPAP를 제거한다고 하면

PXXXXAP -> PPXXXAP -> PPAP -> XXXX -> P 이렇게, 삭제를 한 뒤에 앞으로 땡겨오는 작업이 필요하다.

문자열의 길이가 길어질수록 더 많은 연산량을 요구할 것이다.

 

하지만, stack에 문자열의 문자를 하나씩 삽입하며 검사하게 되면

PPPAP -> PP -> PPAP -> P 이렇게 문자열을 땡겨오는 연산 없이 중간에 PPAP를 제거하며 문제를 해결할 수 있게 된다.

 

스택을 활용하여 문제를 해결하는 예시를 보자.

이렇게, 입력 문자열과 스택이 있다고 해보자.

먼저 입력 문자열의 앞부터 삽입을 해보자.

이렇게 P가 삽입될 것이다. 현재 원소로 P가 삽입되면 스택에 PPAP가 순서대로 저장되어 있는지를 검사해야 한다.

(PPAP는 무조건 P로 끝나기 때문에 P가 삽입될 때마다 스택의 원소를 검사한다.)

 

현재는 스택의 Size가 1이므로 검사할 필요가 없다. 계속 삽입해보자.

5번째 문자까지 삽입하게 되면, 위와 같은 형태가 된다.

이 때, 스택에서 총 4개의 문자를 꺼내서 문자열을 만들어보면 PAPP가 된다.

스택은 문자열이 거꾸로 저장되기 때문에, PAPP라면, 실제 문자열에선 PPAP가 될 것이다.

 

즉, 스택에서 PPAP를 발견했기 때문에, 이를 제거해주어야 한다.

스택에서 꺼낸 PPAP를 다시 넣지 않고, P만을 삽입해주면 아래와 같아진다.

다시 남은 문자를 삽입해주자. 마지막까지 삽입해주면 아래와 같아진다.

다시 스택에서 4개의 문자를 꺼내 검사해보면, PAPP임을 확인할 수 있다.

이를 다시 삽입하지 않고, P만을 넣어주면 스택에는 원소 P만 남게 되고, 입력 문자열을 모두 검사하였으므로 최종적으로 스택에 남은 문자는 P 하나가 된다.

 

위에서 설명했듯이, PPAP를 모두 제거했을 때 P만 남는다면 해당 문자열은 PPAP문자열이기 때문에 현재 주어진 문자열은 PPAP문자열이 맞다고 추론할 수 있다.

 

풀이 코드

std::string Input;
std::cin >> Input;

std::stack<char> Stack;

 

문자열을 입력받아주고 스택을 선언하였다.

for (int i = 0; i < Input.size(); i++)
{
    Stack.push(Input[i]);

    if (Stack.size() >= 4 && Input[i] == 'P')
    {
        std::string Str = "";
        for (int j = 0; j < 4; j++)
        {
            Str.push_back(Stack.top());
            Stack.pop();
        }

        if(Str == "PAPP")
        {
            Str = "P";
        }

        for (int j = Str.size() - 1; j >= 0; j--)
        {
            Stack.push(Str[j]);
        }
    }
}

 

반복문을 돌며, 입력 문자열의 문자를 하나씩 스택에 넣어주었다.

현재 스택에 삽입한 문자가 P이고, 스택에 4개 이상의 원소가 있다면 위에서부터 4개의 원소를 꺼내 검사해주었다.

만약 스택에서 꺼낸 문자들이 PAPP라면 해당 문자를 제거하고, 스택에는 P를 다시 삽입해주었다.

만약 PAPP가 아니라면, 그대로 다시 stack에 넣어주었다.

 

if (Stack.size() == 1 && Stack.top() == 'P')
{
    std::cout << "PPAP";
}
else
{
    std::cout << "NP";
}

return 0;

 

반복문이 종료되었을 때, Stack에 남은 것이 'P' 하나라면, 현재 문자열은 PPAP문자열이 맞다고 판단하여 PPAP를 출력해주었고, 다른 경우엔 NP를 출력해주었다.

 

코드 전문

#include <iostream>
#include <vector>
#include <stack>

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;

    std::stack<char> Stack;

    for (int i = 0; i < Input.size(); i++)
    {
        Stack.push(Input[i]);

        if (Stack.size() >= 4 && Input[i] == 'P')
        {
            std::string Str = "";
            for (int j = 0; j < 4; j++)
            {
                Str.push_back(Stack.top());
                Stack.pop();
            }

            if(Str == "PAPP")
            {
                Str = "P";
            }

            for (int j = Str.size() - 1; j >= 0; j--)
            {
                Stack.push(Str[j]);
            }
        }
    }

    if (Stack.size() == 1 && Stack.top() == 'P')
    {
        std::cout << "PPAP";
    }
    else
    {
        std::cout << "NP";
    }

    return 0;
}