[백준][C++] 16120번: PPAP (266)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

16120번: PPAP

 

생각의 흐름

우선 입력이 1,000,000까지라 O(NlogN), O(N) 안에 해결해야겠다는 생각부터 들었다.

그런데 경험상 이런 문자열 처리는 대부분 O(N)에 처리하는 문제였기에, 문자열을 처음부터 끝까지 한 번만 탐색해서 처리하는 방식을 생각하게 되었다.

 

문제는 이해만 하면 간단하다, 문자열을 계속 읽다가 PPAP가 나오면 이를 P로 바꿔주면 된다.

최종적으로 stack에 남아있는 문자열이 "PPAP" or "P"이면 PPAP를 출력해주고, 아니면 NP를 출력해 주면 되는 문제이다.

 

1) 'P'를 만나면 항상 stack에 추가하며, count한다

2) 'A'를 만나면

    2 - 1) 이전까지 count된 'P'가 2개 이상이고 다음 문자가 'P'라면, stack에서 'P'를 2개 제거하고 2칸 건너뛴다.

    2 - 2) 그외의 경우 'A'를 스택에 추가한다.

3) 최종적으로 Stack에 남아있는 문자열을 비교해 주면 된다.

 

나의 코드

#include <bits/stdc++.h>

using namespace std;

string str;
stack<char> st;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> str;

    int before_p_cnt = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == 'P') {
            st.push('P');
            before_p_cnt++;
        } else if (str[i] == 'A') {
            if (before_p_cnt >= 2 && str[i + 1] == 'P') {
                st.pop();
                st.pop();
                st.push('P');
                before_p_cnt -= 1;
                i++;
            } else {
                st.push('A');
            }
        }
    }

    string res = "";
    while (!st.empty()) {
        res += st.top();
        st.pop();
    }
    reverse(res.begin(), res.end());

    if (res == "PPAP" || res == "P") {
        cout << "PPAP";
    } else {
        cout << "NP";
    }

    return 0;
}