LeetCode 36(Valid Sudoku, java)

0. 문제

https://leetcode.com/problems/valid-sudoku/

Valid Sudoku - LeetCode

 

1. 문제 설명

- 문제에서 이중 배열(board)이 주어진다.

- 이중 배열(board)은 수도쿠 문제를 만들기 위해서 생성된 것이다.

- 이 문제의 핵심은 주어진 이중 배열(board)이 수도쿠로써 이상이 없는지 파악하는 것이다.

 

2. 문제 해설

a) 전제 조건

- 우선 문제에서 주어진 조건을 보자.

  → 각 행마다 1~9의 숫자로 채워지고 중복이 없어야 한다.

  → 각 열마다 1~9의 숫자로 채워지고 중복이 없어야 한다.

  → 만약 9 * 9 행렬이 전체 문제라면, 3 * 3 행렬마다 1 ~ 9의 숫자로 채워지고 중복이 없어야 한다.

 

b) 풀이 접근법

- 위 조건을 기반으로 이 문제를 풀기 위해서는 다음과 같은 접근을 할 수 있다. 

  → 이중 배열을 탐색하기 위해서 이중 for문을 사용한다.

  → HashSet을 이용하여 중복을 확인한다.

 

- 이 2가지 개념을 이용하면 위 문제는 충분히 해결할 수 있다.

- 중복이 발생하면 수도쿠에 문제가 있는 것이므로 false를 반환하면 된다.

- 중복이 없다면 수도쿠에는 아무 문제가 없는 것이므로 true를 반환하면 된다.

 

- 다만, HashSet을 사용하는 데 있어서 약간의 노하우가 있어야 쉽게 풀 수 있다. 

- 다음 코드를 살펴보면서 그 노하우가 무엇인지 알아보자. 

   

3. 정답 코드

class Solution {
    public boolean isValidSudoku(char[][] board) {
        
        HashSet<String> set = new HashSet<>();
        
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                char current = board[i][j];
                if(current != '.') {
                    if(!set.add(current + "found in row" + i) ||
                        !set.add(current + "found in column" + j) ||
                        !set.add(current + "found in sub-box" + i / 3 + "," + j / 3)) {
                        return false;                        
                    }
                }
            }
        }
        return true;
    }
}

 

- 위의 코드에서 원소를 저장하는 방식을 잘 살펴보자. 

- 저런 방식을 사용하는 것이 HashSet을 잘 사용하는 일종의 노하우이다.