문제 개요

문제: PPAP

분류: 자료 구조, 문자열, 스택

난이도: 골드4

문제 풀이

스택을 활용하여 풀이했다.

주어진 문자열의 문자를 순차적으로 탐색하며 아래를 수행한다.

• 현재 문자부터 길이 2만큼을 잘라낸 문자열이 "AP"이면
  • 스택의 상위 두 원소가 모두 “P”인 경우, 이들과 잘라낸 문자열 “AP”를 합쳤을 때 “PPAP”가 완성된다.
    이러한 “PPAP”를 “P”로 치환하기 위해 스택의 상위 두 원소를 pop하고 “P”를 push한다.
    이는 결국 스택을 한 번만 pop하는 것과 같다.
    이때 “AP” 두 글자만큼 건너뛰므로 현재 문자를 가리키는 인덱스를 미리 1만큼 더 증가시킨다.
  • 그렇지 않으면 이미 PPAP 문자열이 아니므로 “NP”를 출력하고 종료한다.
• 현재 문자부터 길이 2만큼을 잘라낸 문자열이 “AP”가 아니면
  • 스택에 현재 문자를 push한다.

탐색이 끝난 후 스택에 ”P” 하나만 남아있다면 이는 “PPAP” 문자열을 “P”로 치환한 것이므로 주어진 문자열이 PPAP 문자열이라는 뜻이다. 따라서 “PPAP”를 출력한다.

그렇지 않다면 “NP”를 출력한다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const ppap = fs.readFileSync(filePath).toString().trim();

const solution = (ppap) => {
  let stack = [];
  let top = -1;

  for (let i = 0; i < ppap.length; i++) {
    if (ppap.substring(i, i + 2) === "AP") {
      if (top > 0 && stack[top] === "P" && stack[top - 1] === "P") {
        stack.pop();
        top--;
        i++;
      } else {
        return false;
      }
    } else {
      stack.push(ppap[i]);
      top++;
    }
  }

  if (top === 0 && stack[top] === "P") return true;
  return false;
};

console.log(solution(ppap) ? "PPAP" : "NP");