CodeSignal - sudoku2에 도전

코딩이 너무 많아서 코딩을 잊어버린 엔지니어가 코딩을 기억하기 위해 코팅합니다.
이번에는, 미국의 코데잉 연습 사이트 CodeSignal의 문제 「sudoku2」를 풀어 갑니다.
사이트에 따르면,이 문제는 Apple, UBER의 인터뷰에서 발생한 것으로 보인다.

문제

9×9 매스의 스도쿠를 나타내는, 이하와 같은 2차원 배열이 주어집니다.

grid = [['.', '.', '.', '1', '4', '.', '.', '2', '.'],
        ['.', '.', '6', '.', '.', '.', '.', '.', '.'],
        ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
        ['.', '.', '1', '.', '.', '.', '.', '.', '.'],
        ['.', '6', '7', '.', '.', '.', '.', '.', '9'],
        ['.', '.', '.', '.', '.', '.', '8', '1', '.'],
        ['.', '3', '.', '.', '.', '.', '.', '.', '6'],
        ['.', '.', '.', '.', '.', '7', '.', '.', '.'],
        ['.', '.', '.', '5', '.', '.', '.', '7', '.']]

스도쿠를 아시는 분이라면 알겠다고 생각합니다만, 스도쿠의 룰에서는, 세로 9매스, 가로 9매스, 3×3의 범위 각각으로 1~9의 문자가 중복해서는 안됩니다.
3×3의 범위라고 하는 것은, 다음의 틀내의 것을 의미하고 있습니다.



이 문제에서는 위의 세 가지 점을 확인하고 조건을 충족하면 ture를 반환하고 그렇지 않으면 false를 반환하는 함수를 작성합니다.

예를 들어, 위의 예라면 세로 9매스, 가로 9매스, 3×3의 범위 어느 것을 체크해도 수치는 중복하지 않기 때문에, 대답은 true입니다.

한편, 아래의 예라면 대답은 false입니다.
중간의 하단의 3×3의 범위에 2가 2회 등장하고 있기 때문입니다.

grid = [['.', '.', '.', '.', '2', '.', '.', '9', '.'],
        ['.', '.', '.', '.', '6', '.', '.', '.', '.'],
        ['7', '1', '.', '.', '7', '5', '.', '.', '.'],
        ['.', '7', '.', '.', '.', '.', '.', '.', '.'],
        ['.', '.', '.', '.', '8', '3', '.', '.', '.'],
        ['.', '.', '8', '.', '.', '7', '.', '6', '.'],
        ['.', '.', '.', '.', '.', '2', '.', '.', '.'],
        ['.', '1', '.', '2', '.', '.', '.', '.', '.'],
        ['.', '2', '.', '.', '3', '.', '.', '.', '.']]

풀기 · 생각

우선 보통으로 생각하면, 세로, 가로, 3×3의 각각에 대해서 중복을 확인해, 어느 하나라도 중복이 있으면 그 시점에서 false를 돌려주면 좋지요.

,,,,

그 밖에 떠올랐습니다.
Java로 쓰면 이런 느낌입니다.

boolean sudoku2(char[][] grid) {
    boolean answer = true;
    HashSet<Character> seen = new HashSet<>();
    char target;

    // check row
    for (int i=0; i<grid.length; i++) {
        seen.clear();
        for (int j=0; j<grid[i].length; j++) {
            target = grid[i][j];
            if (seen.contains(target) && target != '.') {
                return false;
            } else {
                seen.add(target);
            }
        }
    }

    // check column
    for (int i=0; i<grid.length; i++) {
        seen.clear();
        for (int j=0; j<grid[i].length; j++) {
            target = grid[j][i];
            if (seen.contains(target) && target != '.') {
                System.out.println("check column false");
                return false;
            } else {
                seen.add(target);
            }
        }
    }

    // check subgrid
    for(int startRow=0; startRow<9; startRow+=3){
        for(int startColumn=0; startColumn<9; startColumn+=3){
            //loop inside grid
                seen.clear();
            for(int i=startRow; i<startRow+3; i++){
                for(int j=startColumn; j<startColumn+3; j++){
                    target = grid[i][j];
                    if(seen.contains(target) && target != '.') {
                        return false;
                    } else {
                        seen.add(target);
                    }
                }
            }

        }
    }
    return true;
}

코드 설명: seen이라는 HashSet을 준비하고, 그 안에 체크한 수치를 넣어 중복되어 있는지 확인하고 있습니다. 체크하는 관점이 3개이므로, 각각 위에서 행(//　check row의 개소), 열(//check column의 개소), 3×3(//check subgrid의 개소)와 덩어리가 있습니다.

그런데, 이것으로도 테스트는 통과했습니다만, 다른 쪽의 코드를 보면 보다 훨씬 좋은 방법이 있었습니다.
그대로 전재는 미묘하기 때문에, 아이디어는 팩이라고 코드는 조금 바꾸어 게재합니다.

boolean sudoku2(char[][] grid) {
    Set<String> seen = new HashSet<String>();

    for (int i=0; i<grid.length; i++){
        for (int j=0; j<grid.length; j++){
            if (grid[i][j] != '.' && !seen.add(grid[i][j] + " in row " + i)) {return false;}
            if (grid[i][j] != '.' && !seen.add(grid[i][j] + " in col " + j)) {return false;}
            if (grid[i][j] != '.' && !seen.add(grid[i][j] + " in row " + i/3 + " " + j/3)) {return false;} 
        }
return true;
    }
}

코드 설명: seen 에 체크한 값을 넣는 것은 이전의 코드와 같습니다만, 이 경우는 루프는 2 개 밖에 사용하고 있지 않습니다. 2차원 배열의 값을 선두부터 하나씩 체크해 가고, 단지 체크한 값을 넣는 것이 아니라, 이런 느낌으로 문자열로서 보존합니다.
1 in row 0
1 in column 0
1 in subgrid 0
이 덕분에, 예를 들면 같은 1에서도 「X행째에 나온 1」 「X열째에 나온 1」 「여기의 3×3으로 나온 1」과 같이 다른 것으로 저장할 수 있습니다.
따라서 루프는 한 번이라도 단번에 세 가지 관점에서 중복을 확인할 수 있습니다.
마지막으로, HashSet의 add는 추가하려는 값과 동일한 값이 이미 있으면 false를 반환하므로 false의 경우 (중복되는 경우)는 return false로 설정합니다.

이 사고방식에 도착하기 위해서는 우선 루프를 적게 하려고 하는 것이라고 생각합니다.
다음으로, 확인 관점이 3개 있다고 해서, 같은 값을 다른 곳에서 각각 확인하는 것은 낭비,라고 하는 사고방식을 하지 않으면 안 되는 생각이 듭니다.
여기까지 오면 위의 예처럼 스마트하게는 풀 수 없어도, 「그럼 HashSet를 3개 만들어, 배열의 값을 하나씩 보고 가면서 각각에 격납해 가자」, 등의 발상이 태어날 것 같습니다.