[백준 16120] PPAP(Java)

최민길(Gale)·2023년 12월 1일
1

알고리즘

목록 보기
159/172

문제 링크 : https://www.acmicpc.net/problem/16120

이 문제는 스택을 이용하여 풀 수 있습니다. 처음에 백트래킹으로 문자열의 모든 부분을 탐색하는 방식으로 진행했는데 메모리 초과가 발생했습니다. 조금 더 생각해보니 그리디 방식으로 앞에서부터 PPAP 문자열이 완성되면 바로바로 P로 치환해도 정답이 같기 때문에 스택으로 진행했습니다.

문자를 탐색하면서 스택에 담고, 스택의 사이즈가 4 이상일 경우 스택을 4번 pop해서 나온 문자열이 PPAP일 경우 스택에 P만을 추가하고 그 외의 경우 pop한 문자열을 다시 순서대로 스택에 추가합니다. 이 때 마지막 스택의 사이즈가 1이고 그 피크값이 P일 경우 PPAP이기 때문에 그 값을 출력합니다.

다음은 코드입니다.

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

class Main{
    static String PPAP = "PPAP";
    static Stack<Character> stack = new Stack<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        for(int i=0;i<str.length();i++){
            char curr = str.charAt(i);
            stack.add(curr);

            if(stack.size() >= 4){
                String tmp = "";
                for(int j=0;j<4;j++) tmp = stack.pop() + tmp;

                if(tmp.equals(PPAP)) stack.add('P');
                else for(int j=0;j<4;j++) stack.add(tmp.charAt(j));
            }
        }

        if(stack.size()==1 && stack.peek()=='P') System.out.println("PPAP");
        else System.out.println("NP");
    }
}

업로드중..

profile
저는 상황에 맞는 최적의 솔루션을 깊고 정확한 개념의 이해를 통한 다양한 방식으로 해결해오면서 지난 3년 동안 신규 서비스를 20만 회원 서비스로 성장시킨 Software Developer 최민길입니다.

0개의 댓글

관련 채용 정보