[BEAKJOON / node.js] 16120 PPAP

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

// test.txt
'PPAPPAP'

---

sol1

let P = require('fs').readFileSync('test.txt').toString().trim().split('');
function solution(P) {
  let stack = [];
  for(let i=0;i<P.length;i++) {
    stack.push(P[i]);
    if(stack.length >= 4) {
      if(stack[stack.length-1] === 'P') {
        if(stack.slice(-4).join('') === 'PPAP') {
          stack.splice(-4);
          stack.push('P');
        }
      }
    }
  }
  return stack.length === 1 && stack[stack.length-1] === 'P' ? 'PPAP' : 'NP'
}
console.log(solution(P));

1.

stack을 만들어주고 for문을 통해서 P 배열을 하나씩 담는다. stack의 길이가 4 이상이 된다면, 현재 stack에 있는 요소로 PPAP를 만들 수 있는지 계속 검토한다. 만약 PPAP가 만들어진다면, stack의 끝에서부터 4자리를 지워주고, 'P'를 넣어준 후 for문을 계속 돌게 된다.

 

결국 문제의 답이 되려면 for문이 끝났을 때 stack에는 'P'만 남아있어야 한다. 세 번째 if문은 PPAP를 없애면서 동시에 'P'를 붙이기 때문인데 return에 length === 1 인 경우 'PPAP'를 출력하도록 하면 제출 시 98%에서 틀리게 된다. 구체적으로 length가 1이고 그 요소는 'P'인 경우에 'PPAP'가 되도록 조건을 줘야 맞출 수 있었다. stack에 남은 요소가 'A'일 수는 없고 length가 0이 될 수도 없는데 length 조건 만으로 답이 나오지 않는 이유는 찾지 못했다.

 

sol2

const P = require('fs').readFileSync('test.txt').toString().trim();
function solution(P) {
  let cnt = 0;
  let flag = true;
  for (let i = 0; i < P.length; i++) {
      if (P[i] === 'A') {
          if (cnt >= 2 && P[i + 1] === 'P') {
              cnt -= 2;
          } else { 
              flag = false;
              break;
          }
      } else cnt++;
  }
  return cnt === 1 && flag ? 'PPAP' : 'NP';
}
console.log(solution(P));

1. 

sol1 은 입력을 배열로 받아 풀었지만, sol2는 문자열 인체로 해결한다. 문자열을 'PP' 'A' 'P'로 나눠서 보았다. 즉, 'A'를 만났을 때 앞의 문자열에 'PP'가 있고 다음 문자가 'P' 인지 확인한다.

'PPAPPAP'
// 'PPAP'를 지나면서 cnt는 1이 된다.
// 'PAP' 를 지나도 cnt는 1이다.

즉 'PPAP' 문자열이 완성된다면 cnt는 1이 남을 수밖에 없다.

 

2.

else { 
    flag = false;
    break;
}

두 번째 if문인 'A'의 뒤에 'PP'가 있고 앞에 'P'가 있는 경우가 아니라면 항상이 답이 될 수 없다. 따라서 false를 주고 for문을 종료하면 된다.

---

 sol1의 경우 문제를 처음 봤을 때 문자열 폭발 문제와 비슷한 방식으로 해결할 수 있겠다 생각해서 stack으로 해결했다. 아무래도 stack을 하나 더 만들어서 비교하며, 배열의 길이를 조절하는 sol1 보다 문자열 그대로 두고 for문으로 순회하면 끝인 sol2 가 메모리 낭비도 덜하면서 빠르다. 간단한 규칙을 찾을 수 있는 문제인지 잘 파악하는 게 코드를 더 효율적으로 만들 수 있는 것 같다.