[백준] 10942 팰린드롬? - javascript

📌 문제

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

📌 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

let n = +input[0];
let m = +input[2];
let nums = input[1].split(' ').map(Number);
let dp = Array.from({ length: n + 1 }, () => Array.from({ length: n + 1 }, () => 0));
let ans = [];
nums.unshift(0);

for (let i = 1; i <= n - 1; i++) {
  dp[i][i] = 1;
  if (nums[i] === nums[i + 1]) dp[i][i + 1] = 1;
}
dp[n][n] = 1;

for (let diff = 2; diff <= n; diff++) {
  for (let startIndex = 1; startIndex + diff <= n; startIndex++) {
    let endIndex = startIndex + diff;
    if (dp[startIndex + 1][endIndex - 1] && nums[startIndex] === nums[endIndex]) dp[startIndex][endIndex] = 1;
  }
}

input.slice(3).map((i) => {
  const [start, end] = i.split(' ').map(Number);
  ans.push(dp[start][end]);
});
console.log(ans.join('\n'));

✔ 알고리즘 : DP

✔ 길이가 3이상인 (index 범위가 start ~ end) 부분문자열의 팰린드롬 판단을 하기 위해서는 start와 end의 값이 같은지, start+1 ~ end-1 부분문자열이 팰린드롬인지 확인하는 식으로 DP 방식으로 풀었다.

✔ 길이가 1,2인 부분문자열을 초기화 시켜준다.

for (let i = 1; i <= n - 1; i++) {
  dp[i][i] = 1;
  if (nums[i] === nums[i + 1]) dp[i][i + 1] = 1;
}
dp[n][n] = 1;

✔ 간격을 2부터 1씩 늘려가며 팰린드롬인지 판단한다

for (let diff = 2; diff <= n; diff++) {
  for (let startIndex = 1; startIndex + diff <= n; startIndex++) {
    let endIndex = startIndex + diff;
    if (dp[startIndex + 1][endIndex - 1] && nums[startIndex] === nums[endIndex]) dp[startIndex][endIndex] = 1;
  }
}

❗ 출력하는 부분에서 push하고 join으로 출력하지 않고

console.log(dp[start][end])

방식으로 출력을 하면 ❌시간초과❌가 발생한다

✔ 난이도 : 백준 기준 골드 3