[99클럽 코테 스터디] 12일차 TIL - 이분탐색, Count Negative Numbers in a Sorted Matrix

[12일차] 이분탐색

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

* 대충 번역: 행과 열이 모두 내림차순으로 정렬된 m*n 행렬인 grid가 주어질 때, grid의 음수를 모두 반환하라.

Solution

정렬된 행렬에서 원소를 찾기 위해서 이진탐색을 활용할 수 있다.

 

행과 열이 모두 내림차순 정렬되어 있으므로, 오른쪽 위 모서리에서 시작하여 왼쪽 아래로 이동하며 전체를 순회하지 않고도 원하는 원소를 찾을 수 있다. 즉 오른쪽 위 모서리(출발)에서 오른쪽 또는 아래로만 이동하며 원하는 원소를 찾는 방법이다.

이는 이진 탐색의 핵심 아이디어인 "검색 범위를 효율적으로 줄여 나가는" 것이기 때문에, 이진 탐색 알고리즘을 적용한다고 볼 수 있다.

class Solution(object):
    def countNegatives(self, grid):
        row_count = len(grid)
        col_count = len(grid[0])
        result = 0

        # 맨 오른쪽 위에서 시작하여 왼쪽 아래로 이동
        row = 0
        col = col_count - 1

        while row < row_count and col >= 0:
            if grid[row][col] < 0:
                # 이 열의 아래 모든 행은 음수
                result += row_count - row
                col -= 1
            else:
                row += 1

        return result

* 출처: chatgpt

나다어

나는 음수 원소 밑과 옆(오른쪽)으로는 전부 음수라는, 정답과 같은 아이디어를 떠올리기는 했는데 구현하는 과정에서 꼬여버렸다. 풀다 살짝 졸아버린 것은 안 비밀 ,, 

# 틀린 코드
class Solution(object):
    def countNegatives(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # 내림차순이므로
        # 0 미만인 순간부터 쭉이다.
        # m - (0미만인덱스)

        m = 0 # len(grid) - 1
        n = len(grid[0]) - 1

        idx = len(grid)-1
        result = 0

        for col in range(len(grid)):
            for row in range(n):
                if grid[col][row] < 0:
                    n = row - 1
                    result += idx - row
                    break  

        return result

나와 하단의 정답 코드의 반복 부분이 동일한 것으로 보아 아이디어는 같았음을 알 수 있다. 그러나 나는 순회 방법으로 for문을, 정답은 while문을 사용하며 정확성에서 차이가 생긴 것 같다.

 

• 이중 for문이 복잡해진다면 while문을 사용해보자. 최종 구현에 사용하지 않더라도 간결하게 아이디어를 찾을 수 있다.