반응형
1. 문제
- 현재 주어진 스도쿠 정보를 바탕으로(빈 칸 무시) 스도쿠 룰에 적합한 스도쿠인 지 판단하라.
2. 해결
function isValidSudoku(board: string[][]): boolean {
const rowMap = new Map<number, Set<number>>();
const colMap = new Map<number, Set<number>>();
const boxMap = new Map<number, Set<number>>();
for(let i = 0; i < board.length; i++) {
for(let j=0; j < board[i].length; j++) {
const number = Number(board[i][j]);
if(Number.isNaN(number)) continue;
const truncX = Math.trunc(i / 3), truncY = Math.trunc(j / 3)
const boxIdx = truncX * 3 + truncY;
if(rowMap.has(i) && rowMap.get(i).has(number)
|| colMap.has(j) && colMap.get(j).has(number)
|| boxMap.has(boxIdx) && boxMap.get(boxIdx).has(number)) return false;
if(!rowMap.has(i)) rowMap.set(i, new Set<number>([number]));
if(!colMap.has(j)) colMap.set(j, new Set<number>([number]));
if(!boxMap.has(boxIdx)) boxMap.set(boxIdx, new Set<number>([number]));
rowMap.get(i).add(number);
colMap.get(j).add(number);
boxMap.get(boxIdx).add(number);
}
}
return true;
};
- 0~9 까지의 행열을 key로 하는 rowMap, colMap에 Set을 저장해 중복을 체크하고, 0~8까지의 공간을 key로 하는 boxMap을 활용해 서브 박스 내의 중복을 체크한다.