백준 16120 PPAP

작성일 | In |

Problem : PPAP

유형 : 스택

문제 해석

  • 주어진 문자열이 PPAP 문자열 인지 확인하라

문제 재해석

  • PPAP문자열 내 3개의 문자 P를 PPAP로 치환 시킨 것은 PPAP 문자열이다.
  • 치환 시킨 것을 또 치환 시켜도 된다.

해결 전략

  • 문자열 길이가 100만 이다. nlogn 이하로 해결 해야 한다.
  • PPAP를 찾기 위해 전부를 매번 탐색할경우 복잡도가 n^2 이 된다.
  • 순차적으로 탐색 하다가 PPAP 가 등장한 경우 P로 치환 시켜준다.
  • 스택의 괄호쌍 문제들과 똑같은 방식으로 해결할 수 있다

설계 구현

  • 스택을 이용하여 문자열을 쌓아 올려 가본다.
  • 스택 내에서 PPAP 가 완성된 경우 P로 치환한다.

주의할 점

  • P는 PPAP 문자열이다.
  • PP는 NP 이다.
  • PPPAPPAPAP는 PPAP 문자열을 두번 변화 시킨 PPAP 문자열이다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#include <regex>
using namespace std;

string str, s;

void PPAP_check() {
    string PPAP_checker = "";
    for (int i = 0; i < 4; ++i) {
        PPAP_checker = s.back() + PPAP_checker;
        s.pop_back();
    }
    if (PPAP_checker == "PPAP") s += "P";
    else s += PPAP_checker;
}

bool Solve() {
    for (const char &c : str) {
        s.push_back(c);
        if (s.size() >= 4) PPAP_check();
    }
    if (s == "P" or s == "PPAP") return true;
    else return false;
}

void Input() {
    cin >> str;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    if (Solve()) cout << "PPAP\n";
    else cout << "NP\n";

    return 0;
}

피드백

  • 문제 이해가 제대로 안되어서 백준내 게시판을 보고 겨우 이해했다.
  • 문제 해결력도 중요하지만, 문제 이해력도 키워야 할 것 같다.
  • greedy로도 분류가 되어있는데..
    • 최선을 택하니까 그런것인가?
    • 그러면 거의 모든 괄호쌍 문제들도 greedy로 택해야 하는것이 아닌가? 헷갈린다.