[백준] 10942번, 팰린드롬? (JavaScript)

MinKyu Tae·2022년 12월 26일

Algorithm

📌 문제 정보 : 팰린드롬?

문제 분류 : 다이나믹 프로그래밍 (DP)
문제 출처 : 백준 골드 4, 팬린드롬?

✅ 접근 과정

문제의 요구조건을 보았을 때, 주어진 수열에서 특정 범위의 숫자들이 팬린드롬인지 여부를 바로 도출해야 한다는 것을 알 수 있었다.
따라서 2차원 배열의 DP를 사용한다면 해당 범위의 값을 바로 알 수 있을 것이라 생각하고 문제를 풀이했다.

주어진 입력 : [ 1, 2, 1, 3, 1, 2, 1 ]에 대한 dp 결과

✨ 풀이 코드 (1번째)

const readFileSyncAddress = "/dev/stdin";
let input = require("fs")
  .readFileSync(readFileSyncAddress)
  .toString()
  .split("\n");

const N = Number(input[0]);
const nums = input[1].split(" ").map(Number);
const tc = Number(input[2]);
const answer = [];

const dp = Array.from({ length: N }, () => new Array(N).fill(false));

for (let i = 0; i < N; i++) {
  const stack = [nums[i]];
  const std = nums[i];
  dp[i][i] = true;

  for (let j = i + 1; j < N; j++) {
    let src = 0;
    let dst = j - i;

    stack.push(nums[j]);

    // 시작과 끝이 다르면 X.
    if (std !== nums[j]) continue;

    let isPossible = true;

    // 투 포인터
    while (src <= dst && isPossible) {
      if (stack[src] !== stack[dst]) {
        isPossible = false;
        break;
      }

      src++;
      dst--;
    }

    if (isPossible) dp[i][j] = true;
  }
}

input.slice(3, 3 + tc).forEach((el) => {
  const [src, dst] = el.split(" ").map(Number);
  if (dp[src - 1][dst - 1]) answer.push(1);
  else answer.push(0);
});

console.log(answer.join("\n"));

팰린드롬을 구할 때, stack에 값을 하나씩 쌓고 투 포인터 방식을 사용해서 팬린드롬인지 여부를 확인했다.
이 코드로 정답을 맞출 수 있었다.

✨ 풀이 코드 (2번째)

const readFileSyncAddress = "/dev/stdin";
let input = require("fs")
  .readFileSync(readFileSyncAddress)
  .toString()
  .split("\n");

const N = Number(input[0]);
const nums = input[1].split(" ").map(Number);
const tc = Number(input[2]);
const answer = [];
const dp = Array.from({ length: N }, () => new Array(N).fill(false));

for (let i = 0; i < N; i++) {
  dp[i][i] = true;
  if (i + 1 < N) {
    if (nums[i] === nums[i + 1]) dp[i][i + 1] = true;
    else dp[i][i + 1] = false;
  }
}

for (let j = 2; j < N; j++) {
  for (let i = 0; i < N - 1; i++) {
    if (nums[i] !== nums[j]) continue;

    if (dp[i + 1][j - 1]) dp[i][j] = true;
  }
}

input.slice(3, 3 + tc).forEach((el) => {
  const [src, dst] = el.split(" ").map(Number);

  if (dp[src - 1][dst - 1]) answer.push(1);
  else answer.push(0);
});

console.log(answer.join("\n"));