문제
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
Example 1:
Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Example 2:
Input: board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.작성한 코드
나름 성능을 향상시키려고 배열 대신 객체를 쓰고 key 가 존재하는지 여부로 중복 여부를 체크하려고 했다. 그러나 3번째 조건 sub-boxes 에서 유효성을 판단하는 부분은 배열을 쓰지 않고서는 코드가 생각나지 않아서 통과는 되지만 성능이 처참했다.
이후 Set 을 활용해야 함을 알게 되었지만 마찬가지로 3번째 조건에 Set 을 어떻게 적용할 수 있는지에 대해서는 잘 이해가 되지 않았다.
처음 코드
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function(board) {
const startPoints = [0, 3, 6, 27, 30, 33, 54, 57, 60];
const hasValidRow = board.map((row) => isValidRow(row)).reduce((result, val) => result * val);
const hasValidColumn = flipMatrix(board).map((row) => isValidRow(row)).reduce((result, val) => result * val);
const hasValidMatrix = startPoints.map((start) => isValidRow(convertedArray(board, start))).reduce((result, val) => result * val);
return hasValidRow * hasValidColumn * hasValidMatrix;
};
function isValidRow(row) {
let obj = new Object();
for (let i = 0; i< row.length; i++) {
let key = string_to_num(row[i]);
if (key !== 0 && isValidKey(key, obj)) {
obj[`${key}`] = true;
continue
}
if (key !== 0 && !isValidKey(key, obj)) return false;
}
return true;
}
function flipMatrix(matrix) {
const n = matrix.length;
const m = matrix[0].length;
const flippedMatrix = new Array(m).fill(null).map(() => new Array(n));
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
flippedMatrix[j][i] = matrix[i][j];
}
}
return flippedMatrix;
}
function isValidKey(key, obj) {
return key_in_field(key) && key_without_repitation(key, obj);
}
function convertedArray(board, start) {
const flatedMatrix = board.flat();
const resultArray = [];
const targetIndex = [];
targetIndex.push(start, start+1, start+2, start+9, start+10, start+11, start+18, start+19, start+20);
for (let val of targetIndex) {
resultArray.push(flatedMatrix[val])
};
return resultArray;
}
// 언어 레벨
function string_to_num(str) {
if (!isNaN(+str)) return +str;
return 0;
}
function key_in_field(key) {
return key > 0 && key < 10;
}
function key_without_repitation(key, obj) {
return !obj.hasOwnProperty(key);
}계층에 맞게 함수를 구분하여 코드를 작성하려 했는데 시간복잡도를 잘 잡지 못했다.
그리고 공간복잡도 측면에서는
let obj = new Object(); 로 매번 새로운 메모리를 할당하는 것보다 const obj = {}; 같은 방식을 사용하는게 좀 더 성능이 약간 개선된 모습을 보였다.
수정한 최종 버전
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function(board) {
const startPoints = [0, 3, 6, 27, 30, 33, 54, 57, 60];
const hasValidRow = board.map((row) => isValidRow(row)).reduce((result, val) => result * val);
if (!hasValidRow) return false;
const hasValidColumn = flipMatrix(board).map((row) => isValidRow(row)).reduce((result, val) => result * val);
if (!hasValidColumn) return false;
const hasValidMatrix = startPoints.map((start) => isValidRow(convertedArray(board, start))).reduce((result, val) => result * val);
if (!hasValidMatrix) return false;
return true;
};
function isValidRow(row) {
const seen = new Set();
for (const cell of row) {
if (cell !== '.' && (seen.has(cell) || cell < '1' || cell > '9')) {
return false;
}
seen.add(cell);
}
return true;
}
function flipMatrix(matrix) {
const n = matrix.length;
const m = matrix[0].length;
const flippedMatrix = new Array(m).fill(null).map(() => new Array(n));
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
flippedMatrix[j][i] = matrix[i][j];
}
}
return flippedMatrix;
}
function convertedArray(board, start) {
const flatedMatrix = board.flat();
const resultArray = [];
const targetIndex = [start, start+1, start+2, start+9, start+10, start+11, start+18, start+19, start+20];
for (let val of targetIndex) {
resultArray.push(flatedMatrix[val])
};
return resultArray;
}결국 Set 을 활용해야 하는 문제였는데 row 이든, column 이든, matrix 이든 배열 하나만 주어지면 Set 을 사용하는 isValidRow 를 통해 유효성을 검증하도록 코드를 짰는데 matrix 의 경우 해당하는 9개의 값이 담긴 배열을 얻기까지의 과정이 순탄하지 못했다.
시간복잡도 측면에서 객체를 사용하는 것보다 Set 을 사용하는게 좀더 이점이 있는 것 같은데 관련 자료를 찾아봤다.
Set원시값이나 객체 레퍼런스든 상관없이 아무 타입이든 유일한 값을 저장하게 해주는 객체
add - Set 내에 같은 값이 없을때 새 요소를 삽입
clear - Set 객체 내의 모든 요소를 제거
delete - 특정 값을 제거
forEach - 배열의 forEach 와 동일
has - 특정 요소를 갖고있는지 여부를 반환
해시 테이블 자료구조를 갖고 있어 검색 속도가 빠르고 삽입, 삭제 작업이 O(1) 이다. 그러나 순서가 있는 배열에 어울리지 않고 공간 복잡도가 높으며 해시 함수의 의존도가 높다. 해시 충돌이 발생할 수 있다.
SetvsArray값의 존재 유무 확인
- Array :
array.includes()=> O(n)- Set :
set.has()=> O(1)값 추가
- Array :
array.push()=> O(1)- Set :
set.add()=> O(1)특정 값 삭제
- Array :
array.filter()=> O(n)- Set :
set.delete()=> O(1)
중복된 데이터가 없고 값의 존재 여부를 확인하고 특정 값을 삭제하는 행위가 많을 때 Set 을 사용하면 좋다.
레퍼런스
docs
mdn - set
blog
jiwonyyy - set vs array
