2319. Check if Matrix Is X-Matrix

문제파악 및 재정의

 

X-Matrix 조건을 만족하면 True 아니면 False를 반환하라.
다음 조건이 모두 충족되는 경우 정사각형 행렬을 X-행렬이라고 합니다.

행렬의 대각선에 있는 모든 요소는 0이 아닙니다.
다른 모든 요소는 0입니다.
정사각형 행렬을 나타내는 n x n 크기의 2D 정수 배열 그리드가 주어지면
 그리드가 X-매트릭스이면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

자료구조 및 알고리즘 선택

 

 i j        i j        i j        i  j
[0][0] 2 | [1][0] 0 | [2][0] 0 | [3][0] 4
[0][1] 0 | [1][1] 3 | [2][1] 5 | [3][1] 0
[0][2] 0 | [1][2] 1 | [2][2] 2 | [3][2] 0
[0][3] 1 | [1][3] 0 | [2][3] 0 | [3][3] 2

완전 탐색해야 결과가 나옴
[i][j] 순회하며 조건걸어서 찾는게 최선일까

구현

1차 시도 -> 외곽에 0을 채우기만 하면 되는거라고 문제파악을 잘못함

class Solution {
    public boolean checkXMatrix(int[][] grid) {
        boolean answer = true;
        int n = grid.length;
        for (int i = 0; i < n; i++){
            if(!answer) break;
            for(int j = 0; j < n; j++){
                int temp = grid[i][j];
                if(((i == 0 || i == n - 1) && (j != 0 && j != n-1)) || ((j == 0 || j == n - 1) && (i != 0 && i != n-1))){
                    if(temp != 0){
                        answer = false;
                        break;
                    }
                } else {
                    if(temp == 0){
                        answer = false;
                        break;
                    }
                }
            }
        }
        return answer;
    }
}

2차시도 (Runtime 2 ms | Memory 43.4MB)

class Solution {
    public boolean checkXMatrix(int[][] grid) {
        boolean answer = true;
        int n = grid.length;
        for (int i = 0; i < n; i++){
            if(!answer) break;
            for(int j = 0; j < n; j++){
                int temp = grid[i][j];
                if((i == 0 && j == 0) || (i == n-1 && j == n - 1) || (i + j == n-1) || (i == j)){
                    if(temp == 0){
                        answer = false;
                        break;
                    }
                } else {
                    if(temp != 0){
                        answer = false;
                        break;
                    }
                }
            }
        }
        return answer;
    }
}

 

회고

1ms

class Solution {
    public boolean checkXMatrix(int[][] grid) {
      int n = grid.length;
      for(int i = 0; i < n; i ++) {
          for(int j = 0; j < n; j ++) {
              if(i == j || i + j == n - 1) {
              if(grid[i][j] == 0) return false;
              }
              else if(grid[i][j] != 0) return false;
          }
      } 
      return true; 
    }
}

42.5 MB 

class Solution {
    public boolean checkXMatrix(int[][] grid) {
        for (int row = 0; row < grid.length; row++)
            for (int col = 0; col < grid.length; col++)
                if (!isValid(row, col, grid))
                    return false;
        return true;
    }

    private boolean isValid(int row, int col, int[][] grid) {
        if (row == col) return grid[row][col] > 0;
        if (grid.length-row-1 == col) return grid[row][col] > 0;
        return grid[row][col] == 0;
    }
}