| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 2355 | 695 | 524 | 30.715% |
문제
bryan은 PPAP를 좋아한다. bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다.
PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 정확하게는 다음과 같이 정의된다.
- P는 PPAP 문자열이다.
- PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다.
예를 들어 PPAP는 PPAP 문자열이다. 또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP 역시 PPAP 문자열이다.
문자열이 주어졌을 때, 이 문자열이 PPAP 문자열인지 아닌지를 알려주는 프로그램을 작성하여라.
입력
첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.
출력
첫 번째 줄에 주어진 문자열이 PPAP 문자열이면 PPAP를, 아닌 경우 NP를 출력한다.
접근
길이의 최대가 100만이기에 브루트 포스로는 풀리지 않는다.
따라서, 순회하면서 바로바로 문제를 해결할 수 있어야 된다.
'P'와 'A' 두 개의 문자가 있는데, 이중 핵심은 'A'이다.
'A' 이전에 최소 2개의 'P'가 존재해야되며, 'A'의 이후에는 'P'가 와야된다.
따라서, 'P'의 갯수를 counting 해주면서, 'A'를 만날때 조건을 확인하면 된다.
모두 순회했을때, 결과는 "P" 이여만 하므로, counting 된 값은 1이여야 된다.
풀이
p 변수를 만들어, 입력이 'P'일 때 +1 작업을 해주었다.
'A'를 만나면, p가 2 이상인지 확인하고, 다음 인덱스의 문자가 'P'인지 확인한다.
조건에 만족한다면 p값을 1 낮추고, i를 2칸 증가시킨다. ("PPAP" -> "P"로 바뀌기에)
순회한 이후 p 값이 1이 아니면 "NP"를 출력한다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
string str;
int p = 0;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN(str);
int i = 0;
while (i < str.length())
{
if (str[i] == 'P')
{
p++;
i++;
}
else
{
if (p >= 2 && i != str.length() - 1 && str[i + 1] == 'P')
{
p--;
i += 2;
}
else
{
p = -1;
break;
}
}
}
p == 1 ? COUT("PPAP") : COUT("NP");
return 0;
}