49일 (1582. Special Positions in a Binary Matrix) matrix

Given an m x n binary matrix mat, return the number of special positions in mat.

A position (i, j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

 

 

Example 1:

Input: mat = [[1,0,0],[0,0,1],[1,0,0]]
Output: 1
Explanation: (1, 2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

Example 2:

Input: mat = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: (0, 0), (1, 1) and (2, 2) are special positions.


Constraints:
m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] is either 0 or 1.

 

 

행의 원소의 합이 1이고, 열의 원소의 합도 1인 경우의 개수의 합을 리턴하면 된다.

 

- 접근방법

1. 행의 합이 1이면서 열의 합도 1인 경우를 Special Position이라고 하며 Special Position의 합을 구하여야한다.
2. i행의 모든 열의 합이 1이여야한다. 그리고 1이 있는 i행의 열의 위치를 j를 알아야한다.
3. 2의 조건을 만족하는 경우 1이 위치하는 j열에 해당하는 모든 행의 합도 1이여아한다.

 

 

- 코드

class Solution {
    public int numSpecial(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int idx = 0;
        int answer = 0;

        for(int i = 0; i < m; i++) {
            int sum = 0;

            for(int j = 0; j < n; j++) {
                if(mat[i][j] == 1) {
                    sum += mat[i][j]; // 1
                    idx = j; // 2
                }
            }

            if(sum == 1) { // 3
                sum = 0;
                for(int k = 0; k < m; k++) {
                    sum += mat[k][idx];
                }
            }

            if(sum == 1) { // 4
                answer++;
            }

        }

        return answer; // 5
    }
}

 

 

1.  i행의 모든 열의 합이 1인지 판별하기 위해 i번째 행의 모든 열을 변수 sum에 더한다.

 

2. mat[i][j] = 1일때  j의 인덱스를 기억하기 위해 변수 idx에 j를 담는다.

 

3. sum == 1이라면 i행의 모든 열의 합은 1이며, 변수 idx는 1이 담긴 j열의 위치를 나타낸다.

(j열의 위치에 해당하는 모든 행의 합도 1인지 구한다.)

 

4. special Position에 해당한다면 변수 answer에 누적한다.

 

5. special Position에 해당하는 answer를 리턴한다.

 

 

 

https://leetcode.com/problems/special-positions-in-a-binary-matrix

Special Positions in a Binary Matrix - LeetCode