본문 바로가기
개발/알고리즘

[LeetCode] Valid Sudoku

by 자몬다 2021. 1. 15.

 

주어진 2차원 배열 형태의 스도쿠 문제가 유효한지 리턴하는 문제다.

leetcode.com/explore/featured/card/top-interview-questions-easy/92/array/769/

 

Explore - LeetCode

LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore.

leetcode.com

풀이

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
  let boxArr = [[], [], []];
  for (let i = 0; i < 9; i++) {
    // test rows
    if (!isUniq(board[i].filter((item) => item !== "."))) return false;

    const columnArr = [];
    for (let j = 0; j < 9; j++) {
      const item = board[j][i];
      if (item === ".") continue;
      columnArr.push(item); // make column Array
      boxArr[Math.floor(j / 3)].push(item); // make box Array
    }

    if (!isUniq(columnArr)) return false; // test columns
    if (i % 3 === 2) {
      // test boxes
      if (boxArr.some((b) => !isUniq(b))) return false;
      boxArr = [[], [], []];
    }
  }

  return true;
};

var isUniq = (noDotArr) => {
  const noDup = Array.from(new Set(noDotArr));
  return noDotArr.length === noDup.length;
};

 

  2차원 배열, 중복 for문에서 내가 얼마나 혼란스러워하는지 알 수 있는 문제였다.

  그래도 시작하자마자 isUniq 메서드를 만들고, 

  row, column, box 순서대로 차근차근 찍어보면서 푸니

  크게 막히지 않고 풀 수 있었다.

 

 

최종 제출용으로 축약하기 전, 차근차근 찍어가며 풀었던 버전도 남겨둔다.

더보기
var isValidSudoku = function (board) {
  // test rows
  for (let i = 0; i < 9; i++) {
    const uniq = isUniq(removeDot(board[i]));
    // console.log(uniq)
    if (!uniq) return false;
  }

  // test columns
  for (let i = 0; i < 9; i++) {
    const columnArr = [];
    for (let j = 0; j < 9; j++) {
      // console.log(j, i)
      if (board[j][i] !== ".") columnArr.push(board[j][i]);
    }
    // console.log(columnArr)
    // console.log(isUniq(columnArr))
    if (!isUniq(columnArr)) return false;
  }

  // test boxes
  let boxArr1 = [];
  let boxArr2 = [];
  let boxArr3 = [];
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      // console.log(j, i)
      const item = board[j][i];
      if (item === ".") continue;
      if (j < 3) boxArr1.push(item);
      if (2 < j && j < 6) boxArr2.push(item);
      if (5 < j && j < 9) boxArr3.push(item);
    }
    if (i % 3 === 2) {
      console.log(111, boxArr1, boxArr2, boxArr3);
      console.log("========");
      console.log("첫째줄", boxArr1);
      if (!isUniq(boxArr1)) return false;
      boxArr1 = [];

      console.log("========");
      console.log("둘째줄", boxArr2);
      if (!isUniq(boxArr2)) return false;
      boxArr2 = [];

      console.log("========");
      console.log("셋째줄", boxArr3);
      if (!isUniq(boxArr3)) return false;
      boxArr3 = [];
    }
  }

  return true;
};

var isUniq = (noDotArr) => {
  const noDup = Array.from(new Set(noDotArr));
  return noDotArr.length === noDup.length;
};

var removeDot = (arr) => {
  const noDot = arr.filter((item) => item !== ".");
  return noDot;
};

 

728x90

'개발 > 알고리즘' 카테고리의 다른 글

[LeetCode] Reverse Integer  (0) 2021.01.20
[LeetCode] Rotate Image, Reverse String  (0) 2021.01.20
[LeetCode] Valid Sudoku  (0) 2021.01.15
[LeetCode] Move Zeros, Two Sum  (0) 2021.01.15
[LeetCode] Plus One  (0) 2021.01.12
[LeetCode] Single Number, Intersection of Two Arrays II  (0) 2021.01.12

댓글0