99클럽 코테 스터디 13일차 1351. Count Negative Numbers in a Sorted Matrix

https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/description/

 

문제 설명

여러분은 m x n 크기의 정수 행렬 grid를 가지고 있습니다. 이 행렬은 다음과 같은 속성을 가지고 있습니다:

• 각 행의 값은 비내림차순으로 정렬되어 있습니다. (즉, 왼쪽에서 오른쪽으로 갈수록 값이 같거나 커집니다)
• 각 열의 값도 비내림차순으로 정렬되어 있습니다. (즉, 위에서 아래로 갈수록 값이 같거나 커집니다)

이 행렬에서 음수 숫자의 개수를 세는 함수를 작성하세요.

 

 

 

풀이

다음과 같은 방법을 시도했다.

 

1. 주어진 2D 행렬을 1D 리스트로 변환

2. 음수의 개수 세기

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        # 1. 2D 행렬을 1D 리스트로 변환
        flat_list = []
        for row in grid:            # 각 행을 순회
            for num in row:         # 행의 각 요소를 순회
                flat_list.append(num)  # 요소를 flat_list에 추가
        
        # 2. 음수의 개수 세기
        negative_count = 0
        for num in flat_list:      # 평탄화된 리스트의 각 요소를 순회
            if num < 0:            # 요소가 음수이면
                negative_count += 1  # 음수 개수에 1을 추가
                
        return negative_count

 

문제는 순탄하게 풀렸으나, 더 좋은 방법이 있었다.

내가 푼 방법의 시간 복잡도는 다음과 같다.

전체 시간 복잡도

• 2D 행렬을 1D 리스트로 변환: O(n×m)
• 음수의 개수 세기: O(n×m)

즉, O(2xnxm) -> O(nxm)의 시간 복잡도를 가진다

하지만 O(n+m)의 시간복잡도를 가지도록 ( 더 효율적으로 ) 풀 수 있는 방법이 있다.

 

정렬된 특성을 활용한 방법은 최악의 경우 O(n+m)로, 대부분의 조건에서는 O(n×m)보다 훨씬 빠르다.

 

 

def countNegatives(grid):
    # 행(row)와 열(column)의 크기
    rows = len(grid)
    cols = len(grid[0])
    
    # 시작 위치를 오른쪽 상단으로 설정
    row = 0
    col = cols - 1
    
    # 음수의 개수를 저장할 변수를 초기화
    count = 0
    
    # 행렬의 경계를 넘지 않는 동안 반복
    while row < rows and col >= 0:
        if grid[row][col] < 0:
            # 현재 요소가 음수인 경우, 이 열의 아래 모든 요소가 음수임을 알 수 있음
            count += rows - row
            # 왼쪽으로 이동
            col -= 1
        else:
            # 현재 요소가 양수이거나 0인 경우, 아래로 이동
            row += 1
    
    return count

코드 설명

1. 변수 초기화: 행의 개수와 열의 개수를 구하고, 탐색을 시작할 위치를 오른쪽 상단(첫 번째 행의 마지막 열)으로 설정
   => 음수의 개수를 구하기 위한 최소한의 실행을 위함
2. 탐색 시작: 현재 위치의 값이 음수인지 확인
   • 음수일 경우: 현재 위치에서 아래에 있는 모든 요소는 음수이므로, 현재 열의 남은 요소 개수(rows - row)를 음수 개수에 더하고,  왼쪽으로 이동
   • 양수일 경우: 음수가 나타나기 전까지는 아래로 이동하면서 계속 탐색
3. 반복 종료: 탐색이 행렬의 경계를 벗어나면 종료하고, 최종적으로 음수의 개수를 반환

 

 

이렇게 하면 정렬된 데이터를 입력받는다는 조건을 십분 활용하여,

O(n+m) 의 시간복잡도로 효율적으로 풀 수 있다.