[LeetCode] 2125. Number of Laser Beams in a Bank

https://leetcode.com/problems/number-of-laser-beams-in-a-bank/description/

Number of Laser Beams in a Bank - LeetCode

leetcode - Number of Laser Beams in a Bank

문제 유형 : 행렬

문제 난이도 : Medium

 

문제

Anti-theft security devices are activated inside a bank. You are given a 0-indexed binary string array bank representing the floor plan of the bank, which is an m x n 2D matrix. bank[i] represents the ith row, consisting of '0's and '1's. '0' means the cell is empty, while'1' means the cell has a security device.

There is one laser beam between any two security devices if both conditions are met:

• The two devices are located on two different rows: r1 and r2, where r1 < r2.
• For each row i where r1 < i < r2, there are no security devices in the ith row.

Laser beams are independent, i.e., one beam does not interfere nor join with another.

Return the total number of laser beams in the bank.

 

도난방지 보안장치가 은행에서 켜져 있습니다.

당신은 바이너리 문자열 배열 bank를 받습니다.

m*n의 크기이고, 각 문자열은 0과 1로 이루어져 있습니다.

각 셀의 '0'은 비어있는 것을 말하고, '1'은 보안장치가 있다는 것을 말합니다.

두 보안장치가 각 조건을 만족하면 하나의 레이저 빔이 있습니다.

• 두 장치는 서로 다른 행에 있습니다.
• 각 행의 사이에 다른 보안장치가 없어야 합니다.

레이저빔은 독립적입니다(다른 레이저에 간섭하지 않습니다)

은행의 레이저빔의 총 개수를 구하시오.

 

 

풀이

보안장치는 위, 아래로 가장 가까운 열에 있는 보안장치와 연결되어 레이저를 생성한다.

이 말은, 0번째 열에 보안장치들이 있고, 1번째 열에는 보안장치가 없는 경우, 2번째 열의 보안장치들과 연결된다는 의미이다.

 

따라서, 문자열을 순차적으로 읽으면서, '1'의 개수 * 지난 줄의 '1'의 개수를 누적하면 되는데, '1'의 개수가 0개인 경우에는, 누적하지도 않고, 지난 줄의 개수도 업데이트하지 않으면 된다.

 

 

코드

C++

static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        const int m = bank.size();
        const int n = bank[0].size();
        if(m < 2) return 0;
        
        int lastCount = 0;
        int sum = 0;

        for(int i = 0; i < m; i++) {
            int cnt = 0;
            for(int j = 0; j < n; j++) {
                if(bank[i][j] == '1') cnt++;
            }
            // 이번 열에 없으면 건너뛰기
            if(!cnt) continue;
            // 레이저 값 누적, 지난 열의 장치개수 업데이트
            sum += lastCount * cnt;
            lastCount = cnt;
        }

        return sum;
    }
};