[알고리즘] 스도쿠 1 - 스도쿠 문제 검증 (Hash Table, HashSet)

leetcode.com/problems/valid-sudoku/

Valid Sudoku - LeetCode

 

스도쿠 문제가 유효한지 아닌지 검사하는 코드에 대한 문제

스도쿠 문제의 힌트 값들이 들어있는 2차원 배열이 주어지고 행,열,3x3 박스안에서 중복되는 값이 있는지 체크하는 문제이다.

 

Approach 1

행,렬,3x3 박스 각각 3번의 다른 범위에 대한 중복 체크가 필요하다.

중복을 허용하지 않고 검색이 쉬운 HashSet 을 사용하였다.

 

HashSet 의 add() 는 값이 이미 있는지 없는지 중복체크 후에 없으면 그 값을 추가하는 method 이다.

HashTable을 사용하여 중복을 체크하기 때문에 O(1) 의 시간복잡도를 갖는다.

저장 성공 여부(중복체크)에 따라 boolean 을 리턴한다.

 

각각 다른 행,렬,박스의 HashSet array를 만들어서 0번째 row 에 있는 값은 HashSet rows[0] 에 추가한다.

같은 방식으로 행/렬/박스/index 별로 값을 저장하면서 동시에 중복 체크를 하여 유효성 검사를 한다.

이미 값이 존재하면 유효하지않은 스도쿠이기 때문에 false 를 리턴한다.

 

Approach 2

 

직접 loop 로 가로,세로,박스를 체크 해주는 건데 (Discuss 컨닝함)

의외로 런타임도 빠르다