[2024] Day3. 2125. Number of Laser Beams in a Bank

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 3일 (수)
Leetcode daily problem

2125. Number of Laser Beams in a Bank

https://velog.io/@heyggun/2024-Day2.-2610.-Convert-an-Array-Into-a-2D-Array-With-Conditions

Problem

주어진 bank의 배열의 원소는 은행의 바닥 평면을 나타내는데, '0'은 셀이 비어 있음을 의미하고, '1'은 보안 장치가 있는 것을 나타낸다. 보안 장치 간에 레이저 빔이 존재하는데, 레이저빔은 아래의 두 가지 조건을 만족해야 한다.
[조건]
1) 두 장치는 서로 다른 행에 위치해야 하고 r1과 r2라고 했을 때, 여기서 r1 < r2입니다.
r1 < i < r2인 각 행 i에는 다른 보안 장치가 없어야 한다.

Solution

주어진 각 행에서 보안 장치의 수('1')를 파악한다.
장치가 있는 마지막 행부터 장치 수를 추적한다.
각 행을 계속 확인하면서 장치가 있는 행을 찾으면 잠재적으로 이전에 만난 행의 장치로 레이저 빔을 형성한다.
형성된 새로운 빔의 수는 현재 행의 장치 수와 이전에 발생한 행의 장치 수를 곱해서 구할 수 있다.
그런 다음 '마지막' 변수를 업데이트하여 현재 행의 장치 수를 유지한다. 업데이트한 장치의 수는 장치가 포함된 다음 행의 빔을 계산하는 데 사용된다.
이 논리에 따라 알고리즘은 행을 반복하면서 빔 수를 계산한다.

Code

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        cnt = 0
        total = 0
        for row in bank:
            cur_cnt = row.count('1')
            if cur_cnt > 0 :
                total += cnt * cur_cnt
                cnt = cur_cnt
        return total

Complexicity

시간 복잡도

back 배열을 반복하면서 돌면서, 배열 내의 원소의 1의 개수를 세야하기 때문에, 전체 시간복잡도는 O(m*n) 이다.

공간 복잡도

상수 개수의 변수만 사용하므로 공간 복잡도는 O(1)이다.

---