백준 16120번 PPAP JAVA 구현해보기

---

```

백준 16120번 PPAP JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 16120번 풀이

---

 

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

16120번: PPAP

 

백준 16120번 PPAP는 

난이도 실버 등급의 문제로서

 

PPAP는 P로 변경 가능할 때

P와 A로 이루어진 문자열이 주어지면

해당 문자열이 P로부터 파생된 문자열인지 아닌지를 판단하면 되는 문제입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

첫 시도

PPAP로 이루어진 문자를

String의 기본 contains 함수로 확인 후 있으면 치환해서

P를 찾았습니다.

다만 시간 초과이기 때문에 다른 방법을 찾았습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {

        if (isPpapStr()) {
            System.out.println("PPAP");
        } else {
            System.out.print("NP");
        }
    }

    private static boolean isPpapStr() throws IOException {
        boolean isPpap = false;
        String str = br.readLine();
        while (true) {
            if (!str.contains("PPAP")) {
                break;
            }
            if (str.equals("PPAP")) {
                isPpap = true;
                break;
            }
            str = str.replaceAll("PPAP", "P");
        }
        return isPpap;
    }
}

 

아래는 통과한 방법입니다.

복잡도는 O(n)이며

PPAP를 치환할 때

맨 앞에서부터 A를 기준

A앞에 P의 개수

A 뒤에 P의 개수는

각 2개 1개임으로

개수를 세서 해결하였습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {

        if (isPpapStr()) {
            System.out.println("PPAP");
        } else {
            System.out.print("NP");
        }
    }

    private static boolean isPpapStr() throws IOException {
        boolean isPpap = false;
        String str = br.readLine();
        int strLen = str.length();
        int cnt = 0;

        // 마지막 문자가 P 일 경우 참
        // PPAP 에서 A 앞에는 2개의 P 가 있어야 참
        // PPAP 에서 A 뒤에는 하나의 P 가 있어야 참
        // 갯수를 세면 항상 1 이 여분임
        if(str.charAt(strLen-1) == 'P'){
            isPpap = true;
            for (int i = 0; i < strLen; i++) {
                char curCh = str.charAt(i);
                if (curCh == 'P') {
                    cnt++;
                } else if (curCh == 'A') {
                    if (str.charAt(i + 1) != 'P' || cnt < 2) {
                        isPpap = false;
                        break;
                    }
                    cnt -= 2;
                }
            }
            if (cnt != 1) {
                isPpap = false;
            }
        }
        return isPpap;
    }
}

 

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---