プログラマは最大の正方形を検索します(level 2)
18331 ワード
私の第1ラウンドの解答(解答時間:32分)
function solution(board)
{
var answer = 0;
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
if (board[i][j] === 1) {
let check = true;
for (let count = 1; count <= board.length; count++) {
if (!check) break;
if (i+count < board.length && j+count < board[0].length) {
for (let k = j; k <= j+count; k++) {
if (board[i+count][k] === 0) {
check = false;
break;
}
}
if (check) {
for (let k = i; k <= i+count; k++) {
if (board[k][j+count] === 0) {
check = false;
break;
}
}
}
} else {
break;
}
if (check) answer = Math.max(answer, (count+1)**2);
}
}
}
}
return answer;
}
boardを探索する際,1が見つかった場合,1からcountを増やし,正方形を形成して展開し,元素中に0が存在するかどうかを調べる.0がある場合はcheck変数をfalseに変更します.私の2回目の答え
function solution(board)
{
let answer = 0;
if (board.length < 2 || board[0].length < 2) {
if (board[0].includes(1)) return 1;
}
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
if (board[i][j] === 1 && (Math.min(board.length-i, board[0].length-j) > Math.sqrt(answer))) {
answer = Math.max(1,answer);
let check = true;
for (let count = 1; count <= board.length; count++) {
if (!check) break;
if (i+count < board.length && j+count < board[0].length) {
for (let k = j; k <= j+count; k++) {
if (board[i+count][k] === 0) {
check = false;
break;
}
}
if (check) {
for (let k = i; k <= i+count; k++) {
if (board[k][j+count] === 0) {
check = false;
break;
}
}
}
} else {
break;
}
if (check) answer = Math.max(answer, (count+1)**2);
}
}
}
}
return answer;
}
思いついた例外をすべて処理するために,正確性評価で満点を得た.しかし効率面では通らなかった.いっそ別の方法で近づこう.
Reference
この問題について(プログラマは最大の正方形を検索します(level 2)), 我々は、より多くの情報をここで見つけました https://velog.io/@htogether7/프로그래머스-가장-큰-정사각형-찾기-level-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol