LeetCode 36. Valid Sudoku 자바 문제 풀이

문제

Valid Sudoku - LeetCode

문제 해결 방법

• 이 문제는 수도쿠의 맵을 생성시 그 조건을 체크하는 코드를 생성하는 문제이다.
• Solution 2는 가장 최적화된 코드이고, Solution 1는 분할을 많이하여 나중에 수정을 염두에 둔 코드이다.

Github Link

https://github.com/eunhanlee/LeetCode_36_Valid_Sudoku_Solution.git

Solution 1 시간복잡도: O(1), 공간복잡도: O(1)

import java.util.*;

public class Solution {
    
    /**
     * 주어진 스도쿠 보드가 유효한지 확인합니다.
     *
     * @param board 스도쿠 보드를 2차원 char 배열로 표현합니다.
     * @return 보드가 유효하면 true, 그렇지 않으면 false를 반환합니다.
     */
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    if(chkMetrixHasDuplicate(board, i, j)) return false;
                    if(chkRowHasDuplicate(board, i, j)) return false;
                    if(chkColumnHasDuplicate(board, i, j)) return false;
                }
            }
        }

        return true;
    }

    private boolean chkMetrixHasDuplicate(char[][] board, int i, int j) {
        return hasDuplicate(getMetrix(board, i, j));
    }
    
    private boolean chkRowHasDuplicate(char[][] board, int i, int j) {
        return hasDuplicate(getRow(board, i, j));
    }
    
    private boolean chkColumnHasDuplicate(char[][] board, int i, int j) {
        return hasDuplicate(getColumn(board, i, j));
    }

    /**
     * 위치 (i, j)에 있는 셀을 포함하는 3x3 매트릭스의 값을 가져옵니다.
     *
     * @param board 스도쿠 보드를 2차원 char 배열로 표현합니다.
     * @param i     셀의 행 인덱스입니다.
     * @param j     셀의 열 인덱스입니다.
     * @return 매트릭스에 있는 값들을 나타내는 문자의 리스트입니다.
     */
    private List<Character> getMetrix(char[][] board, int i, int j) {
        List<Character> result = new ArrayList<>();
        int startX = (i/3)*3;
        int startY = (j/3)*3;

        for (int x = startX; x < startX+3; x++) {
            for (int y = startY; y < startY+3; y++) {
                if (board[x][y] != '.') {
                    result.add(board[x][y]);
                }
            }
        }

        return result;
    }
    
    /**
     * 위치 (i, j)에 있는 셀과 동일한 행에 있는 값을 가져옵니다.
     *
     * @param board 스도쿠 보드를 2차원 char 배열로 표현합니다.
     * @param i     셀의 행 인덱스입니다.
     * @param j     셀의 열 인덱스입니다.
     * @return 행에 있는 값들을 나타내는 문자의 리스트입니다.
     */
    private List<Character> getRow(char[][] board, int i, int j) {
        List<Character> result = new ArrayList<>();

        for (int y = 0; y < 9; y++) {
            if (board[i][y] != '.')
                result.add(board[i][y]);
        }

        return result;
    }
    
    /**
     * 위치 (i, j)에 있는 셀과 동일한 열에 있는 값을 가져옵니다.
     *
     * @param board 스도쿠 보드를 2차원 char 배열로 표현합니다.
     * @param i     셀의 행 인덱스입니다.
     * @param j     셀의 열 인덱스입니다.
     * @return 열에 있는 값들을 나타내는 문자의 리스트입니다.
     */
    private List<Character> getColumn(char[][] board, int i, int j) {
        List<Character> result = new ArrayList<>();

        for (int x = 0; x < 9; x++) {
            if (board[x][j] != '.')
                result.add(board[x][j]);
        }

        return result;
    }
    
    /**
     * 문자 리스트에 중복된 값이 있는지 확인합니다.
     *
     * @param list 확인할 문자 리스트입니다.
     * @return 리스트에 중복된 값이 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
     */
    private boolean hasDuplicate(List<Character> list) {
        HashSet<Character> set = new HashSet<>();
        for (char c : list) {
            if (set.contains(c)) {
                return true;
            }
            set.add(c);
        }

        return false;
    }
}

Solution 2 시간복잡도: O(1), 공간복잡도: O(1)

package org.example;

public class Solution2 {
    /**
     * 주어진 스도쿠 보드가 유효한지 확인합니다.
     *
     * @param board 스도쿠 보드를 2차원 char 배열로 표현합니다.
     * @return 보드가 유효하면 true, 그렇지 않으면 false를 반환합니다.
     */
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.' && !valid(board, i, j))
                    return false;
            }
        }

        return true;
    }

    /**
     * 특정 위치 (i, j)에 있는 셀의 값이 유효한지 확인합니다.
     *
     * @param board 스도쿠 보드를 2차원 char 배열로 표현합니다.
     * @param i     셀의 행 인덱스입니다.
     * @param j     셀의 열 인덱스입니다.
     * @return 셀의 값이 유효하면 true, 그렇지 않으면 false를 반환합니다.
     */
    boolean valid(char[][] board, int i, int j) {
        for (int x = 0; x < 9; x++) {
            if (x != i && board[x][j] == board[i][j])
                return false;

            if (x != j && board[i][x] == board[i][j])
                return false;

            int row = i / 3 * 3 + x / 3; // matrix row
            int col = j / 3 * 3 + x % 3; // matrix col

            if ((row != i || col != j) && board[i][j] == board[row][col])
                return false;
        }

        return true;
    }
}