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 가 메모리 낭비도 덜하면서 빠르다. 간단한 규칙을 찾을 수 있는 문제인지 잘 파악하는 게 코드를 더 효율적으로 만들 수 있는 것 같다.
'Study > Algorithm' 카테고리의 다른 글
[BEAKJOON / node.js] 26069 붙임성 좋은 총총이 (0) | 2022.11.19 |
---|---|
[programmers / JavaScript] 연속된 수의 합 (0) | 2022.11.17 |
[BEAKJOON / node.js] 11509 풍선 맞추기 (0) | 2022.07.06 |
[BEAKJOON / node.js] 1946 신입 사원 (0) | 2022.07.04 |
[BEAKJOON / node.js] 1475 방 번호 (0) | 2022.06.29 |