[노드JS/알고리즘] 백준 - 17609번 회문

[문제]

17609번: 회문

[메모리 초과 뜬 코드]

const [_, ...words] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const result = [];
for (const word of words) {
  if (word === word.split("").reverse().join("")) result.push(0); // 회문일 경우
  else {
    let pseudo = false;
    let splited = word.split("");
    for (let i = 0; i < splited.length; i++) {
      splited[i] = "";
      if (splited.join("") === splited.reverse().join("")) { // 유사회문일 경우
        pseudo = true; //유사회문 체크 변수에 true를 넣어줌
        break;
      }
      splited = word.split("");
    }
    pseudo ? result.push(1) : result.push(2);
  }
}

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

유사회문을 체크하는데에서 많은 시간과 메모리를 사용해서 그런지 메모리 초과가 떴다..

배열을 Array.from()으로 미리 할당하고 push 대신 index를 이용해 값을 넣어도 메모리 초과가 떴다. 

[풀이]

const [_, ...words] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

function check(word, left, right) {
  while (left < right) {
    if (word[left] === word[right]) {
      left++;
      right--;
    } else return false;
  }
  return true;
}

function solution(word) {
  let left = 0;
  let right = word.length - 1;

  while (left < right) {
    if (word[left] === word[right]) {
      left++;
      right--;
    } else {
      if (check(word, left + 1, right) || check(word, left, right - 1))
        return 1;
      return 2;
    }
  }
  return 0;
}

const result = [];
for (const word of words) result.push(solution(word));

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

투 포인터를 활용하여 해결하였다.

left 포인터를 증가시켜 오른쪽으로 이동시키거나 right 포인터를 감소시켜 왼쪽으로 이동시켰을 때 true를 반환하면 유사 회문이다.