https://www.acmicpc.net/problem/16120
16120번: PPAP
첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.
www.acmicpc.net
P는 PPAP 문자열이며, P를 PPAP로 바꾼 문자열 역시 PPAP 문자열입니다.
이 조건과 문자열 주어졌을 때 PPAP 문자열인지 판별하는 문제입니다.
우선 문자열의 처음부터 순회를 합니다.
해당 위치의 문자가
'P'이면 cnt를 1 증가합니다.
'A'이면 cnt가 2 이상이고, 다음 문자가 'P'이면 PPAP문자열이므로 PPAP를 P로 변경합니다.
실제 로직으로는 cnt를 1 감소하고, 다음 인덱스가 P인것을 확인했으니 인덱스도 1 증가합니다.
만약 'A'일때 cnt가 2보다 작거나, 마지막 인덱스이거나, 다음 문자가 'P'가 아니면 NP를 출력합니다.
순회가 끝났을때 남는 문자열은 P여야하므로 cnt가 1일때만 PPAP를 출력, 아니면 NP를 출력합니다.
|
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 <iostream>
#include <string>
using namespace std;
string str;
int N;
void func() {
int cnt = 0;
for (int i = 0; i < N; i++) {
if (str[i] == 'P') cnt++;
else {
if (cnt >= 2 && i < N - 1 && str[i + 1] == 'P') {
cnt--;
i++;
}
else {
cout << "NP\n";
return;
}
}
}
if (cnt == 1) cout << "PPAP\n";
else cout << "NP\n";
}
void input() {
cin >> str;
N = str.size();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 2262 토너먼트 만들기 (0) | 2021.10.16 |
|---|---|
| boj 13904 과제 (0) | 2021.09.30 |
| boj 1826 연료 채우기 (0) | 2021.02.22 |
| boj 8980 택배 (0) | 2021.02.16 |
| boj 11000 강의실 배정 (0) | 2021.02.16 |