Top Interview Questions
Easy Collection
LEVEL : 🌕 🌕 🌕 🌑 🌑 (중)
Easy Collection의 열번째 문제인 Valid Sudoku를 풀어봤습니다.
Valid Sudoku는 주어진 이차원 배열 속 스도쿠 숫자들을 통해 해당 스도쿠가 문제가 없는지 확인하는 문제였습니다.
기본적인 스도쿠 규칙대로 같은 행, 열에 같은 숫자가 있으면 안되고, 같은 3*3 칸 속에도 같은 숫자가 있으면 안됩니다. 주어진 이차원 배열이 해당 규칙을 따르는지 확인하면 됩니다.
저는 행, 열을 확인하는 로직은 바로 생각이 났지만 3*3 규칙에 해당하는 로직이 바로 떠오르지 않아서 고민 끝에 Solution 찬스를 썼습니다.
전에 C++로 알고리즘을 짰을 때, 썼던 dfs 방식이 생각나긴 했는데 그 비슷한 방식으로 하던거 같아요!
Solution 코드들을 같이 봅시다.
1️⃣ 번째 방법
첫번째 방식은 row, colum, box(3*3짜리 칸)를 확인하는 Set를 따로 세 개씩두고 확인하는 방식이었습니다.
해당 방식은 저번에 했던 Two Sum때와 동일하게 enumerated()를 사용했는데요.
첫 for문에서는 characterRow 자체를 빼오고 두번째 for문에서는 그 row안에 있는 character들을 하나씩 빼오는 방식이었습니다. 그리고 enumerated()를 사용해서 해당 character의 index를 함께 가져와서 Set으로 만들어져있는 row, columns, boxes에 넣어줬습니다.
만약, 해당 character가 contains = true에 해당한다면 조건에 부합하지 않기 때문에 결론적으로 false를 return하고 아니면 true를 return하도록 해줬습니다.
row, column, box별로 index를 둬서 character가 있는 자리를 표시하도록 했습니다. /3를 해준 이유는 각 칸별로 index를 잡기 위함이에요. 행, 열 총 3*3칸이 한 box를 이루고 있기 때문이죠.
func isValidSudoku(_ board: [[Character]]) -> Bool {
let size = board.count
var columns = (0..<size).map { _ in Set<Character>(minimumCapacity: size) }
var boxes = (0..<size).map { _ in Set<Character>(minimumCapacity: size) }
for (rowIndex, characterRow) in board.enumerated() {
var row = Set<Character>()
for (columnIndex, character) in characterRow.enumerated() {
if character == "." {
continue
}
let rowBoxIndex = Int(rowIndex / 3)
let columnBoxIndex = Int(columnIndex / 3)
let boxIndex = columnBoxIndex + (rowBoxIndex * (size/3))
if row.contains(character) {
return false
}
row.insert(character)
let column = columns[columnIndex]
if column.contains(character) {
return false
}
columns[columnIndex].insert(character)
let box = boxes[boxIndex]
if box.contains(character) {
return false
}
boxes[boxIndex].insert(character)
}
}
return true
}2️⃣ 번째 방법
두 번째 방법도 첫 번째 방법과 비슷합니다. 조금 다른 부분은 String으로 넣어줬고, row, column, grid에 각각 직접 정한 String값을 넣었어요.
하지만 전체적인 방식은 아주 비슷합니다. contains되어있는지 확인하고 아니라면 insert 맞다면 false를 return합니다.
위에서는 enumerated()를 사용한 것과는 다르게 0부터 9까지 이중 for문을 돌렸어요. 어차피 스도쿠 판은 9*9 크기로 한정되어 있기 때문에 그렇습니다.
위에 보다 좀 더 이해하기 쉽고 생각하기도 쉬웠던 로직 같습니다.
func isValidSudoku(_ board: [[Character]]) -> Bool {
var setSudoku = Set<String>()
for i in 0..<9 {
for j in 0..<9 {
if board[i][j] != "." {
let value = board[i][j]
let row = "row:\(i):\(value)"
let column = "column:\(j):\(value)"
let grid = "row:\(i / 3):\(j / 3):\(value)"
if setSudoku.contains(row) || setSudoku.contains(column) || setSudoku.contains(grid) {
return false
} else {
setSudoku.insert(row)
setSudoku.insert(column)
setSudoku.insert(grid)
}
}
}
}
return true
}저는 당연히 있는 숫자들끼리 비교하려고 했는데, 다른 Set를 만들 생각을 왜 못했는지 모르겠네요 🥲
더 노력해야겠습니다.
