[ 백준 16120 ] PPAP (C++) - 그리디

---

🔗 문제 링크

16120번: PPAP

---

💡 문제 풀이 및 해석

1. 원형이 PPAP 인지 확인해야 하는 문제다.
2. P -> PPAP 이므로 역으로 생각하면 PPAP -> P 가 된다고 생각할 수 있다.
3. 그럼 문자열에서 앞에서부터 PPAP 인 부분을 P 로 바꿔가면서 O(N) 으로 탐색하면 된다.

---

⭐️ 정답 코드 및 설명

#include <iostream>
#include <algorithm>

using namespace std;

string sol(string str) {
    string temp = "";
    int tempIndex = 0;
    for (int i = 0; i < str.size(); i++) {
        temp += str[i];
        // cout << temp << endl; 진행 과정을 볼 수 있다.
        if (temp.size() >= 4 && temp.substr(temp.size() - 4, 4) == "PPAP") { // PPAP 라면
            for (int j = 0; j < 3; j++) { // PPAP -> P
                temp.pop_back();
            }
        }
    }
    if (temp == "P") // PPAP 가 남았어도  PPAP -> P 가 되므로 이런 조건을 넣어줌.
        str = "PPAP";
    else {
        str = "NP";
    }
    return str;
}

void input(string &str) {
    cin >> str;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string str;
    input(str);
    cout << sol(str);

    return 0;
}

---

🤔 문제 후기

처음에는 같은 방식에서 temp를 쓰지 않고, 그냥 str에서 erase를 사용하였는데, 생각해보니, 그러면 문자열 앞에서부터 계속 자르게 된다면, O(N)에 푸는 것이 아닌 O(N^2)에 풀게 된다. (erase는 최악의 경우 O(n)) 따라서 다른 방법을 생각해야 했고, 이는 temp라는 임시 string을 만들어서 해결할 수 있었다. 결과적으로 중간에 삽입 된 문자열이므로 보일 때 마다 삭제해주는 그리디 방식(그리디가 맞나?)으로 해주면 된다.