99클럽(2기) - 코테스터디 14일차 TIL # Binary Search

LeetCode - 1351. Count Negative Numbers in a Sorted Matrix

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

• Constraints:
  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • -100 <= grid[i][j] <= 100

---

 

1. 첫 번째 풀이

 풀이는 20분 정도 걸렸지만이중 반복문으로 모든 행과 열을 순회하기 때문에 시간 복잡도가 O(m * n)이다. 모든 행은 다 탐색하더라도 열에 대해서는 이분 탐색을 적용할 수 있을 것 같았지만 해결책이 쉽게 떠오르지 않았다.

 

1) 행렬 순회를 위해 행의 인덱스와 열의 인덱스 초기화

 행의 인덱스 m을 행의 개수로, 열의 인덱스 n을 첫 번째 행의 열의 개수로 초기화해준다. m * n 행렬이므로 첫 번째 행의 열의 개수는 각각의 모든 행의 열의 개수와 동일하다. 행렬을 순회할 때, range(m)과 range(n)과 같이 행과 열의 인덱스를 이용할 것이고 range(n)은 0부터 n-1까지의 범위를 의미하므로 n과 m에 1을 빼지 않고 그대로 사용했다. 

 

2) 모든 행에 대한 모든 열을 순회

 2-1) 첫 번째 열이 음수인 경우

 하나의 행에 대해서 첫 번째 열이 음수인 경우 그 뒤는 볼 것도 없으므로 정답에 모든 열의 개수를 더해준다.

 

 2-2) 첫 번째 열이 음수가 아닌 경우

 하나의 행에 대해서 첫 번째 열이 음수가 아닌 경우 음수가 나올 때까지 순회하다가 음수인 열이 나오면 정답에 '모든 열의 개수에서 음수인 열을 만나기까지 한 칸 오른쪽으로 간 횟수를 빼준 값'을 더해준다.  

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        answer = 0
        m = len(grid) # 행의 개수
        n = len(grid[0]) # 첫 번째 행에 대한 열의 개수 (= 모든 행의 열의 개수)
        
        for i in range(m): # 모든 행에 대해서
            if grid[i][0] < 0: # 첫 번째 열이 음수면
                answer += n # 정답에 모든 열의 개수를 더해준다
            else:
                for j in range(n): # 모든 열에 대해서
                    if grid[i][j] < 0: # 음수인 열이 나오면
                        answer += n - j # 정답에 '모든 열의 개수에서 음수인 열을 만나기까지 진행한 횟수를 빼준 값'을 더해준다
                        break

        return answer

 

 

2. 두 번째 풀이

 오늘도... 나의 쓰앵님 챗지피티에게 도움을 받아 시간 복잡도 O(m + n)으로 개선했다. 행은 맨 마지막에서 맨 첫 번째 방향으로 진행하고, 열은 첫 번째에서 맨 마지막 방향으로 진행해서 대각선 방향으로 만나게 했다. row는 시작 시 m - 1이고 최종적으로 0까지 감소할 수 있어 m번 감소하며, col은 시작 시 0이고 최종적으로 n - 1까지 증가할 수 있어 총 n번 증가할 수 있다. 그런데 각 반복에서 m이나 n 중 하나만 변하기 때문에 전체 시간복잡도는 O(m + n)이 된다.

 

1) 행렬 순회를 위해 행의 인덱스와 열의 인덱스, 행의 개수와 열의 개수 초기화

 행의 개수와 열의 개수는 행렬 순회 시 while문의 조건으로 사용하기 위함이고, 행의 인덱스와 열의 인덱스는 행렬에 해당 인덱스로 접근하기 위해서 사용한다. 

 

2) 현재 열이 음수인지 여부에 따라서 행 이동 또는 열 이동

 행의 인덱스가 0보다 크고 열의 인덱스가 열의 개수보다 작을 때까지만 아래 로직 반복

 2-1) 현재 열이 음수인 경우(행의 진행 방향: 맨 마지막 행 → 맨 첫 번째 행)

 현재 행의 현재 열의 위치가 음수라면 이후의 열은 모두 음수이기 때문에 이 때부터 다음 열을 탐색할 필요가 없다. 정답에 '전체 열의 갯수에서 현재 열의 인덱스를 빼준 만큼' 더한 후 한 칸 위의 행을 탐색하기 위해 행의 인덱스에서 1을 빼준다.  

 

 2-2) 현재 열이 음수가 아닌 경우(열의 진행 방향: 맨 첫번째 열 → 맨 마지막 열)

  현재 행의 현재 열의 위치가 음수가 아니라면 다음 열로 이동해서 음수인지 확인해야 하기 때문에 열의 인덱스에 1을 더해준다.

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m = len(grid) # 행의 개수
        n = len(grid[0]) # 첫 번째 행에 대한 열의 개수 (= 모든 행에 대한 열의 개수)
        answer = 0
        row = m - 1 # 행의 인덱스를 맨 마지막으로 초기화
        col = 0 # 열의 인덱스를 맨 첫 번째로 초기화
        
        while col < n and row >= 0: 
            if grid[row][col] < 0: # 현재 행에 대한 현재 열의 위치가 음수라면
                answer += (m - col) # 정답에 '전체 열의 갯수에서 현재 열의 인덱스를 빼준 만큼' 더함
                row -= 1 # 행을 한 칸 위로 이동
            else: # 음수가 나올 때까지 한 칸 오른쪽으로 이동
                col += 1  
        
        return answer

 

 

3. 느낀점 

 시간복잡도 개념이 왜 중요한지 느껴진다. 로직 개선의 기준이 된달까,, 왜 첫 번째 떠오르는 생각은 항상 시간복잡도가 높은 풀이일까.. 오늘 두번째 풀이를 하면서 행렬 순회의 방향을 바꾸는 것 만으로도 시간복잡도가 O(m * n)에서 O(m + n)으로 줄어드는 것을 경험하며, 복잡한 것을 간단하게 추상화하는 포인트는 간단하면서도 떠올리기 어렵다고 느꼈다. 또, 이러한 능력이 진짜 실력이 아닐까라는 생각을 요즘 참 많이 하게 된다.