백준 16120 PPAP

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

P는 PPAP 문자열이고, PPAP 문자열의 P 하나를 PPAP로 바꾼 것도 PPAP 문자열이다.

주어진 문자열이 PPAP 문자열인지 확인하는 문제이다.

문자열이 주어졌으니, 주어진 문자열에서 PPAP가 등장하면 P로 바꾸고 끝까지 작업을 마쳤을 때, P 하나만 남는 지 찾는 것이 좋겠다 생각하였다.

그래서 첫 번째 풀이 시도에서는, StringBuilder를 이용해 PPAP를 찾으면 P로 바꾼 후 앞으로 3칸 이동하는 것을 반복하는 알고리즘을 작성했다.

하지만 주어지는 문자열의 길이가 최대 1,000,000이므로 시간초과가 발생했다.

그래서 두 번째 풀이로, Int형 변수를 통해 P의 개수를 세며 스택과 유사한 효과를 내도록 해 보았다.

그 알고리즘은 다음과 같다. (변수를 p라고 하면)

1. 현재 문자가 P인 경우 p를 1 증가시킨다.
2. 현재 문자가 A인 경우
   2-1) p가 2 이상이고, 다음 문자가 P라면 - PPAP이므로 p를 2 감소시킴.
   (다음 위치의 P로 이동함으로써 PPAP가 P로 바뀐 효과)
   2-2) 2-1조건을 만족시키지 않으면 break 후 NP 출력.
3. 모든 문자를 순회한 뒤 p값이 1이라면 PPAP 출력.

위 알고리즘을 통해 예시를 풀어보자.

PPPPAPAPAP라는 문자열이 주어졌다.

1. 처음 P 4개를 지나며 p = 4가 된다.
2. 첫 번째 A에서, 바로 다음 문자가 P이므로 p = 2이 된다.
3. 첫 번째 A 다음 P에서 p = 3가 된다.
4. 두 번째 A에서, 바로 다음 문자가 P이므로 p = 1가 된다.
5. 두 번째 A 다음 P에서 p = 2이 된다.
6. 세 번째 A에서, 바로 다음 문자가 P이므로 p = 0이 된다.
7. 세 번째 A 다음 P에서 p = 1이 된다.

모든 문자를 순회한 후 p가 1이므로 PPAP 문자이다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val str = readLine().toCharArray()

    var p = 0
    for(i in str.indices){
        if(str[i] == 'P') p++

        if(str[i] == 'A'){
            if(p >= 2 && i + 1 < str.size && str[i + 1] == 'P')
                p -= 2
            else{
                p = 0
                break
            }
        }
    }

    print(if(p == 1) "PPAP" else "NP")
}