[백준/JS] 1802 종이접기

문제

🧐 문제 풀이

참고블로그

잘못생각한 점

위 사진 처럼 한번만 중심을 기준으로 비교해주면 된다고 생각했습니다.

하지만 이 경우는

위와 같은 경우는 안되는 케이스지만 맞다고 출력하게 됩니다.

다시 생각한 점

위 사진 처럼 중심을 기준으로 모든 대칭점을 확인해 주어야 합니다.

따라서 한번의 반복문을 사용하는 것이 아닌

재귀 함수 를 이용해서 풀어줘야 합니다.

1. 시작과 끝이 같은 경우 true 반환
2. 대칭점이 서로 같은 방향(IN,OUT)인 경우 false 반환

📝 결과 코드

const { parentPort } = require("worker_threads");

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

let tc = Number(input.shift());

let paper = "";

function check(start, end) {
  if (start === end) return true;

  let mid = Math.floor((start + end) / 2);

  for (let i = start; i < mid; i++) {
    if (paper[i] === paper[end - i]) {
      return false;
    }
  }

  return check(start, mid - 1) && check(mid + 1, end);
}

for (let t = 0; t < tc; t++) {
  paper = input.shift().split("");

  if (check(0, paper.length - 1)) {
    console.log("YES");
  } else {
    console.log("NO");
  }
}