99클럽 코테 스터디 14일차 TIL

 

오늘의 공부 키워드

• 1351.Count Negative Numbers in a Sorted Matrix

 

1351.Count Negative Numbers in a Sorted Matrix

이 문제는 m x n 행렬(grid)이 행과 열 모두 내림차순으로 정렬되어 있을 때, 행렬 안의 음수 숫자의 개수를 세는 문제입니다.

문제 이해

주어진 행렬은 각 행과 각 열이 내림차순으로 정렬되어 있습니다 예를 들어 아래 행렬에서는 음수 숫자가 8개 있습니다.

grid = [[4, 3, 2, -1],
        [3, 2, 1, -1],
        [1, 1, -1, -2],
        [-1, -1, -2, -3]]

 

접근 방법

이 문제를 해결하기 위한 효율적인 방법은 다음과 같습니다:

1. 각 행에 대해, 오른쪽에서 왼쪽으로 이동하면서 음수를 찾습니다.
2. 음수를 찾으면, 그 열 이하의 모든 값이 음수라는 것을 알 수 있습니다(왜냐하면 내림차순이기 때문입니다).
3. 따라서 그 지점에서 남은 모든 값을 음수로 간주하고, 음수의 개수를 누적합니다.

구체적인 단계는 다음과 같습니다:

1. 행(row)별로 반복합니다.
2. 각 행의 오른쪽 끝부터 시작하여 왼쪽으로 이동합니다.
3. 음수를 만나면 해당 지점에서 그 행의 끝까지 남은 요소의 개수를 더합니다.
4. 다음 행으로 이동하여 동일한 과정을 반복합니다.

예제

위의 예제 행렬을 통해 설명하면:

• 첫 번째 행: [-1]에서 음수를 만나므로 1개의 음수 발견
• 두 번째 행: [-1]에서 음수를 만나므로 1개의 음수 발견
• 세 번째 행: [-1, -2]에서 음수를 만나므로 2개의 음수 발견
• 네 번째 행: [-1, -1, -2, -3]에서 음수를 만나므로 4개의 음수 발견

이렇게 총 8개의 음수를 발견하게 됩니다.

 

코드

from typing import List

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        count = 0
        # 시작은 마지막 열의 처음 행
        row, col = 0, n - 1
        
        while row < m and col >= 0:
            if grid[row][col] < 0:
                # 음수를 만나면, 해당 열 아래 모든 행이 음수이므로 추가
                count += (m - row)
                col -= 1
            else:
                # 음수를 만나지 않으면 다음 행으로 이동
                row += 1
        
        return count

# 예제 테스트
solution = Solution()

grid1 = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
print(solution.countNegatives(grid1))  # 8

grid2 = [[3,2],[1,0]]
print(solution.countNegatives(grid2))  # 0

 

설명

1. 시작 지점: 맨 위 행(row)의 마지막 열(col)에서 시작합니다.
2. 탐색 방식:
   • 현재 위치의 값이 음수일 경우, 해당 열 이하의 모든 값이 음수임을 알 수 있으므로, 그 수만큼 카운트합니다. 그리고 왼쪽 열로 이동합니다.
   • 현재 위치의 값이 음수가 아닐 경우, 다음 행으로 이동합니다.
3. 반복: 행(row) 또는 열(col)의 끝에 도달할 때까지 반복합니다.
4. 결과 반환: 모든 음수의 개수를 반환합니다.

이 방식은 매번 음수를 만날 때마다 그 아래 모든 값을 계산하기 때문에 더 효율적이며, 시간 복잡도는 최악의 경우 O(m+n))입니다.

 

오늘의 회고

 

• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자
• 새로운 개념을 배울수 있어서 좋았다.