[백준] 16120번. PPAP(JAVA)

문제

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

---

풀이(22분)

import java.io.*;
import java.util.*;

public class Main {

    /*
    시작은 p하나에서 시작된다.
    이 후 모든 p를 p -> ppap로 대체할 수 있다.
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Queue<Character> queue = new LinkedList<>();
        String input = br.readLine();
        int pCount = 0;
        int aCount = 0;
        boolean flag = true;
        for(int i = 0; i < input.length(); i++){
            queue.add(input.charAt(i)); // 큐에 문자열 추가
            if(input.charAt(i) == 'A'){
                aCount++;
            }
        }


        while(queue.size() > 1 && aCount > 0){
            char c = queue.poll();
            if (c == 'P') { // p라면 큐에 추가
                pCount++;
                continue;
            }
            // p가 아니라면
            if(queue.isEmpty()){ // 큐가 끝났다면
                flag = false;
                break;
            }
            if(queue.peek() == 'P'){ // 다음 문자가 P라면
                if(pCount >= 2){
                    aCount--;
                    pCount -= 2;
                    continue;
                }
            }
            flag = false;
            break;
        }

        // flag와 queue.size와 aCount를 모두 참고
        if(flag && queue.size() == 1 && aCount == 0){
            System.out.println("PPAP");
        }else{
            System.out.println("NP");
        }
    }

}

---

문제 풀이 전략

 

예외 처리가 생각보다 힘든 문제였다.

 

풀이를 요약해 보자.

1. 가장 중요한 것은 첫 시작은 무조건 P로 한다는 것이다.

-> 그렇기에 우리는 최종적으로 P만 남은 문자열을 만들어야 한다.

 

2. A가 있으면 PPAP를 만들어낼 수 있는지 본다.

-> A가 문자열의 끝이면 안 된다.

-> 이 전까지 남은 P가 2개 이상 존재해야 한다.

-> 뒤에 나오는 문자가 P여야 한다.

 

2-1. 위 조건을 모두 통과한다면 p -= 2, a -= 1을 해준다.

-> 여기서 p를 3개 전부 빼는 것이 아닌 2개만 빼는 이유는 ppap -> p로 축약된 것이라고 보기 때문이다.

 

2-2. 조건을 만족하지 못한다면 flag = false로 break 해준다.

 

3. 큐에 대한 검사가 모두 끝난 뒤 조건을 체크해 준다.

-> flag == false였다면 이미 만족을 못한다는 것이다.

-> queue.size() == 1이 아니라면 최종적으로 p가 1개보다 많다는 것이므로 안 된다.

-> aCount!= 0이라면 아직 a를 모두 사용하지 못했다는 것으로 안 된다.