파이썬으로 2차원 행렬 효율적으로 검색하기 (Search a 2D Matrix II)

문제 개요

m x n 크기의 2차원 행렬이 주어졌을 때, 이 행렬 안에서 특정 값을 효율적으로 찾는 알고리즘을 작성해야 합니다. 이 행렬은 다음과 같은 두 가지 중요한 특성을 가지고 있습니다.

• 각 행의 정수들은 왼쪽에서 오른쪽 방향으로 오름차순으로 정렬되어 있습니다.
• 각 열의 정수들은 위에서 아래 방향으로 오름차순으로 정렬되어 있습니다.

예를 들어, 행렬이 다음과 같다고 가정해 보겠습니다.

이때 찾으려는 값(target)이 5라면 true를 반환하고, 20이라면 false를 반환해야 합니다.

알고리즘 접근 방법

이 문제의 핵심은 행렬의 오른쪽 상단(우상단) 모서리에서 탐색을 시작하는 것입니다. 우상단 원소는 해당 행에서는 가장 큰 값이면서, 해당 열에서는 가장 작은 값이기 때문에 한 번의 비교로 탐색 범위를 한 줄 또는 한 열씩 확실하게 줄일 수 있습니다.

구체적인 해결 단계는 다음과 같습니다.

• 열의 개수를 구하고, 시작 위치를 첫 번째 행(row)과 마지막 열(column)로 설정합니다. 즉, c1 := 0, c2 := 열 개수 - 1
• 다음 과정을 반복합니다.
  • 현재 위치의 값 matrix[c1][c2]가 target과 같으면 true를 반환합니다.
  • 현재 값이 target보다 크면, 그 열에서 더 아래로 내려갈수록 값만 커지므로 해당 열은 제외하고 c2를 1 감소시켜 왼쪽으로 이동합니다.
  • 현재 값이 target보다 작으면, 그 행에서는 답이 없으므로 c1을 1 증가시켜 아래로 이동합니다.
  • c1이 행 개수 이상이 되거나 c2가 0보다 작아지면 더 이상 탐색할 곳이 없으므로 false를 반환합니다.

이 방식을 사용하면 매번 비교할 때마다 하나의 행 또는 하나의 열 전체를 배제할 수 있어, 시간 복잡도는 O(m + n)으로 매우 효율적입니다.

파이썬 구현 예제

class Solution:
   def searchMatrix(self, matrix, target):
      try:
         length = len(matrix[0])
         counter1, counter2 = 0, length-1
         while True:
            if matrix[counter1][counter2] == target:
               return True
            elif matrix[counter1][counter2]>target:
               counter2-=1
               continue
            counter1 = counter1 + 1
            if counter1 >= len(matrix) or counter2<0:
               return False
         except:
            return False
ob1 = Solution()
print(ob1.searchMatrix([[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], 5))

입력

[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
5

출력

True

코드 설명

위 코드에서 counter1은 현재 행 인덱스, counter2는 현재 열 인덱스를 나타냅니다. 탐색은 항상 우상단에서 시작하며, 값이 크면 왼쪽으로, 값이 작으면 아래로 이동하는 방식으로 진행됩니다. try-except 블록은 빈 행렬이나 잘못된 입력처럼 인덱스 접근이 불가능한 경우에도 안전하게 false를 반환하도록 처리해 줍니다.

예제에서는 5x5 행렬에서 값 5를 찾았고, 실제로 행렬에 존재하므로 True가 출력된 것을 확인할 수 있습니다.