백준 16120번 - PPAP

www.acmicpc.net/problem/16120

16120번: PPAP

그리디 알고리즘이라길래 풀었다가 크게 당한 문제다..

 

그리디 문제를 여러 번 풀수록 내 멍청함에 한 번 감탄하고 내가 풀이법을 떠올리는 것에 또 한 번 감탄한다.

참 신기한 알고리즘이야..

 

이거 풀려고 연습장에 PPAP를 몇 번을 썼는지 모르겠다ㅋㅋ

 

처음에 접근을 완전히 이상하게 해서 너무 많은 시간을 버리고 결국 코드를 처음부터 다시 짰다.

 

먼저 정답을 받은 방법부터 설명하자면 아래와 같다.

 

1. 문자열의 마지막부터 시작하여 하나의 문자씩 확인한다 (딱 봐도 stack이 쓰기 좋겠네요)

 

2. 만약 해당 문자가

 

'P' 라면 : p_cnt++

이때 이미 "AP"가 한 번이라도 나왔고, 현재 P가 2개 이어져있다면(PP라면) PPAP를 만들 수 있기 때문에 P로 변환

-> stack에 p 넣어줌 (사실 이게 내 풀이법의 가장 중요한 핵심 포인트였다고 생각함)

 

'A' 라면 :

A가 나오기 이전에 P가 한 번이라도 나왔다면 AP로 만듦. 

이때 AP가 만들어진 후 이미 나왔던 P는 더 이상 사용하면 안 된다.

-> 예를 들어 APPP 이런 순으로 나왔다면 AP가 하나 만들어지고 뒤의 PP는 사라져야 한다. 그렇지 않으면 다른 A와 결합하게 되고 이는 오답으로 가는 지름길이다.. (이해가 안된다면 두 번째 예제를 돌려보자)

 

A가 나오기 이전에 P가 한 번도 나오지 않았다면 무조건 오답임 (매우 당연한 말임)

 

3. 2번 과정을 계속 반복한 뒤 마지막에 P가 하나만 남는다면 정답! 

 

이 과정으로 구하게 되면 "P"만 입력으로 들어오는 경우도 예외 처리하지 않아도 된다.

 

나는 이 방법 전에 되게 이상하고 복잡한 방향으로 구현했었는데 이 방법을 떠올리고 난 뒤에는 후..

 

지금 생각해보니 굳이 stack을 사용하지 않고도 앞에서부터 확인하면 더 쉬웠을 것 같긴 한데.. 

또 이상한 풀이법에 꽂혀서 이 지경까지 와버린 것 같다ㅠㅠ

 

#include <iostream>
#include <stack>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    string str; bool stop = false;
    stack <char> s;
    int ap_cnt = 0, p_cnt = 0;
    cin >> str;
    for (int i = 0; i < str.size(); i++) s.push(str[i]);
    while (!s.empty()) {
        if (s.top() == 'P') {
            p_cnt++;
            s.pop();
            if (ap_cnt > 0 && p_cnt >= 2) {
                ap_cnt -= 1;
                p_cnt -= 2;
                s.push('P');
            }
        }
        else {
            if (p_cnt < 1) { // A가 나왔는데 뒤에 P가 없다면 무조건 오류
                stop = true;
                break;
            }
            else {
                ap_cnt++;
                p_cnt = 0;
            }
            s.pop();
        }
    }
    if (stop) cout << "NP" << "\n";
    else {
        if (p_cnt == 1 && ap_cnt == 0) cout << "PPAP" << "\n";
        else cout << "NP" << "\n";
    }
}