[백준] 1051 숫자 정사각형 JavaScript

혅·2024년 6월 4일

백준, 프로그래머스 -JavaScript-

목록 보기

42/215

문제

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

예제 입력

3 5
42101
22100
22101

예제 출력

내가 했던 풀이 방법

N과 M을 저장하고, 둘 중 더 작은 값을 min에 저장한다. 여기서 min은 가로/세로의 최대를 의미하게 된다.
N×M의 square 배열을 선언하고, 입력받은 수를 배열에 저장해준다.
max를 0으로 초기화해주고, 2차원 배열을 순서대로 순회하면서 해당 요소를 start에 저장해준다. 길이(k)를 0부터해서 최대 길이만큼 늘려주면서, width, height, end를 저장해준다. 이때 end는 start와 대각선 방향에서 만나는 꼭짓점을 의미한다. width, height, end에 해당하는 수가 모두 같을 경우에 (k+1)^2을 해준 결과가 max보다 클 경우, max를 대체해준다. 만약 i+k, j+k 중 하나라도 index를 벗어나는 경우 해당 연산을 중단한다. (k를 0부터 min-1까지 진행하는 이유는 k가 0인 것은 길이가 1임을 의미한다. 그러므로, 정사각형의 크기를 구할 때 k+1을 해주어야 의도한 결과와 같게 나온다.)
모든 요소에 대해 연산을 끝낸 뒤 max를 출력해준다.

코드

const fs = require('fs');
let [n, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let N = Number(n.trim().split(' ')[0]);
let M = Number(n.trim().split(' ')[1]);
let min = Math.min(N, M);

let square = Array.from({ length: N }, () => new Array(M));
for (let i = 0; i < N; i++) {
  input[i] = input[i].trim().split('').map(Number);
  for (let j = 0; j < M; j++) {
    square[i][j] = input[i][j];
  }
}

let max = 0;
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    let start = square[i][j];
    for (let k = 0; k < min; k++) {
      if (i + k >= N || j + k >= M) break;
      let width = square[i][j + k];
      let height = square[i + k][j];
      let end = square[i + k][j + k];
      if (width === height && height === end && end === start) {
        max = max < (k + 1) ** 2 ? (k + 1) ** 2 : max;
      }
    }
  }
}

console.log(max);