티스토리 뷰
728x90
반응형
문제 요약
- 알고리즘 분류: 구현
- 난이도: Medium
- 문제내용:
- 문자형으로 스토쿠 배열을 준다. '.'은 비어 있는 공간이다.
- 스도쿠를 보고 유효한 스도쿠인지 반환하여라.
- 사이트 주소: https://leetcode.com/problems/valid-sudoku/description/
문제풀이
이번 문제는 스도쿠 빈칸을 채우는 문제가 아니라 스도쿠판을 주고 이 판이 유효한지만 체크 하면된다. 그럼 구현 할것은 크게 2개라고 보면된다.
- 가로, 세로 중복된 숫자 여부
- 3 × 3 Box 안에 중복된 숫자 여부
숫자 일때 아래 2개를 확인 하면 된다.
1. 가로, 세로 중복된 숫자 여부
자기 위치 빼고 가로 세로 중복된 숫자 있는지 확인하면 된다.
Python
def isCross(x, y, num):
for i in range(9):
if (i != y and board[x][i] == num) or (i != x and board[i][y] == num):
return False
return True
Java
public boolean isCross(int x, int y, int num){
for(int i = 0; i < 9; i++){
if((i != x && sudokuBoard[i][y] == num)|| (i != y && sudokuBoard[x][i] == num)){
return false;
}
}
return true;
}
2. 3 × 3 안에 중복된 숫자 여부
x - (x % 3), y - (y % 3)는 박스의 시작점이다. 박스안에 중복된 숫자 있는지 확인하면 된다.
Python
def isBox(x, y, num):
# 박스 가로, 세로 시작점
boxX = x - (x % 3)
boxY = y - (y % 3)
for i in range(3):
for j in range(3):
if ((boxX + i != x) and (boxY + j != y)) and board[boxX + i][boxY + j] == num:
return False
return True
Java
public boolean isBox(int x, int y, int num){
int boxX = x - (x % 3);
int boxY = y - (y % 3);
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
if((boxX + i != x && (boxY + j != y) ) && sudokuBoard[i+boxX][j+boxY] == num){
return false;
}
}
}
return true;
}
스도쿠 판중에 거짓 하나라 나오면 거짓으로 반환하고 다 탐색하고 이상없으면 참으로 반환하기만 된다.
이번 문제는 스도쿠 판을 채울수 있는가였으면 백트레킹으로 풀면되지만 이 문제는 단순 스도쿠 판만 주고 유효한지만 판단하면 되기 때문에 어렵지 않을것이라고 생각한다. 자세한것은 아래 코드를 참조하기만 하면된다.
Code
Python
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# 가로, 세로 중복 숫자 찾는 함수
def isCross(x, y, num):
for i in range(9):
if (i != y and board[x][i] == num) or (i != x and board[i][y] == num):
return False
return True
# 박스안에 중복 숫 찾는 함수
def isBox(x, y, num):
# 박스 가로, 세로 시작점
boxX = x - (x % 3)
boxY = y - (y % 3)
for i in range(3):
for j in range(3):
if ((boxX + i != x) and (boxY + j != y)) and board[boxX + i][boxY + j] == num:
return False
return True
# 스토쿠 유효하는 판단하는 함수
def isSudoku(x, y, num):
return isCross(x, y, num) and isBox(x, y, num)
for i in range(9):
for j in range(9):
# 유효하지 않는 스토구는 바로 반환한다.
if board[i][j] != '.' and (not isSudoku(i, j, board[i][j])):
return False
return True
Java
class Solution {
int[][] sudokuBoard;
public boolean isValidSudoku(char[][] board) {
sudokuBoard = new int[9][9];
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
sudokuBoard[i][j] = board[i][j] == '.'? 0 : board[i][j] - '0';
}
}
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(sudokuBoard[i][j] != 0 && !isSudoku(i, j, sudokuBoard[i][j])){
return false;
}
}
}
return true;
}
/*
* 가로 세로 숫자가 있는지 판별하는 메소드
*/
public boolean isCross(int x, int y, int num){
for(int i = 0; i < 9; i++){
if((i != x && sudokuBoard[i][y] == num)|| (i != y && sudokuBoard[x][i] == num)){
return false;
}
}
return true;
}
/*
* 가로 세로 숫자가 있는지 판별하는 메소드
*/
public boolean isBox(int x, int y, int num){
int boxX = x - (x % 3);
int boxY = y - (y % 3);
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
if((boxX + i != x && (boxY + j != y) ) && sudokuBoard[i+boxX][j+boxY] == num){
return false;
}
}
}
return true;
}
/*
* 스도쿠 판별 가능한지 확인하는 메소드
*/
public boolean isSudoku(int x, int y, int num){
return isCross(x, y, num) && isBox(x, y, num);
}
}
728x90
반응형
'알고리즘 > Leetcode' 카테고리의 다른 글
[Leetcode]807. Max Increase to Keep City Skyline (0) | 2024.08.01 |
---|---|
[Leetcode]3137. Minimum Number of Operations to Make Word K-Periodic (0) | 2024.07.30 |
[Leetcode]2740. Find the Value of the Partition (0) | 2024.07.13 |
[Leetcode]3111. Minimum Rectangles to Cover Points (0) | 2024.06.26 |
[Leetcode]1282. Group the People Given the Group Size They Belong To (0) | 2024.06.07 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 그리디
- DP
- Greedy
- 백트레킹
- 알고리즘
- BFS
- 조합
- JSCODE
- 자바
- 문자열
- spring-boot
- 수학
- 이론
- LeetCode
- 배열
- 그래프
- DFS
- 구현
- 넓이 우선 탐색
- 백준
- 재귀호출
- 동적계획법
- 파이썬
- 힙
- 누적합
- Python
- Programmerse
- level2
- java
- 동적 계획법
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함