[알고리즘 연습] 백준 1025 (제곱수 찾기, 자바스크립트)

문제

1025번: 제곱수 찾기

---

풀이

N * M인 2차원 배열이 주어졌을 때, 행의 번호와 열의 번호가 선택한 순서대로 등차수열을 이루는 서로 다른 1개 이상의 칸을 선택하여 정수를 만든다. 만들 수 있는 정수 중 가장 큰 완전 제곱수를 출력하고 완전 제곱수를 만들 수 없는 경우 -1를 출력한다.

• 4중 for 문을 통해 배열의 모든 위치에서 가능한 모든 등차를 탐색한다.
• while 문을 통해 주어진 등차로 위치를 증가시키며 완전 제곱수인지 확인한다.

소스 코드

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

const [N, M] = input[0].split(" ").map((el) => +el);
const arr = Array.from({ length: N }, () => Array(M).fill(null));
let answer = -1;

for (let i = 1; i <= N; i++) {
  const temp = input[i].split("").map((el) => +el);
  for (let j = 0; j < M; j++) {
    arr[i - 1][j] = temp[j];
  }
}

// 최대 약 9 * 9 * 18 * 18
// 시작 위치 : (x, y), 등차 : (i, j)
for (let x = 0; x < N; x++) {
  for (let y = 0; y < M; y++) {
    for (let i = -N; i < N; i++) {
      for (let j = -M; j < M; j++) {
        if (i === 0 && j === 0) continue; // 등차가 없을 때

        let posX = x;
        let posY = y;
        let target = 0;

        // 등차로 증가하면서 하나씩 계속 확인한다.
        while (posX >= 0 && posX < N && posY >= 0 && posY < M) {
          target *= 10;
          target += arr[posX][posY];

          if (check(target)) answer = Math.max(answer, target);

          posX += i;
          posY += j;
        }
      }
    }
  }
}

console.log(answer);

function check(target) {
  const sqrt = Math.floor(Math.sqrt(target));

  if (sqrt * sqrt === target) return true;
  else return false;
}