[리트코드] 10일차

36. Valid Sudoku

문제 이해를 잘못해서매우 어려웠던 문제.....

스토쿠가 풀리는 문제인지 확인하는 것인줄알았는데...

그게 아니라 그냥 있는 숫자들 바탕으로 스토쿠가 되는지 확인하는 문제였다.

그래서 이해하고 나서는 간단하게 해결할 수 있었다.

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<Character>[] rows = new HashSet[9];
        HashSet<Character>[] cols = new HashSet[9];
        HashSet<Character>[] boxes = new HashSet[9];

        for (int i =0; i < 9; i++){
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }

        for (int r = 0; r < 9; r++){
            for (int c = 0; c < 9; c++){
                if (board[r][c] == '.') {
                    continue;
                }

                char num = board[r][c];

                int boxIndex = (r / 3) * 3  + (c/3);

                if (rows[r].contains(num) || cols[c].contains(num) || boxes[boxIndex].contains(num)){
                    return false;
                }

                rows[r].add(num);
                cols[c].add(num);
                boxes[boxIndex].add(num);
            }
        }
        return true;

    }
}

 

54. Spiral Matrix

어렵지 않은문제였다고 생각했는데 꽤나 어려웠다...

공식을 찾는게 제일 어려웠던 것 같다. 공식만 찾으면 쉽게 풀리는 문제였다.

 

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int x= 0;
        int y = 0;
        int dx = 1;
        int dy = 0;

        List<Integer> res = new ArrayList<>();

        for (int i =0; i< rows * cols; i++){
            res.add(matrix[y][x]);
            matrix[y][x] = -101;

            if (! (0 <= x + dx && x + dx < cols && 0 <= y + dy && y + dy < rows) || matrix[y+dy][x+dx] == -101){
                int temp = dx;
                dx = -dy;
                dy = temp;
            }
            x += dx;
            y += dy;
        }

        return res;
    }
}

 

48. Rotate Image

추억이 새록새록 나는 문제였다. 대학교 1학년 때 비슷한 문제 풀다가 새벽 4시까지 풀었는데..ㅎㅎ 그것보다는 쉬운 문제였다.

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] rotateMatrix = new int[n][n];
        for (int r = 0; r < n; r++){
            for (int c = 0; c < n; c++){
                rotateMatrix[r][c] = matrix[n-c-1][r];
            }
        }
        for (int r = 0; r < n; r++){
            for (int c = 0; c < n; c++){
                matrix[r][c] = rotateMatrix[r][c];
            }
        }
    }
}

저 의미없는 matrix 의 값을 다시 넣어주는 로직을 없애고 싶다...

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        for (int r = 0; r < n; r++) {
            for (int c = r; c < n; c++) {  
                int temp = matrix[r][c];
                matrix[r][c] = matrix[c][r];
                matrix[c][r] = temp;
            }
        }

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n / 2; c++) {
                int temp = matrix[r][c];
                matrix[r][c] = matrix[r][n - c - 1];
                matrix[r][n - c - 1] = temp;
            }
        }
    }
}

찾아본 결과 이런 코드가 존재했다. 전치행렬로 하는방식인데 이것마저도 for 문을 두번 돌긴한다. 공간은 그만큼 절약된 것을 확인할 수 있었다.