Python으로 이진 행렬에서 가장 왼쪽에 있는 1의 열 인덱스 찾기

2차원 이진 행렬이 주어졌다고 가정해 보겠습니다. 이 행렬의 각 행은 오름차순으로 정렬되어 있어, 모든 0이 1보다 먼저 나타납니다. 우리의 목표는 값이 1인 가장 왼쪽 열의 인덱스를 찾는 것이며, 만약 1이 존재하지 않는다면 -1을 반환해야 합니다.

예를 들어 입력이 다음과 같다고 해보겠습니다.

이 경우 출력은 2입니다. 인덱스 2번째 열에 행렬 전체에서 가장 왼쪽에 위치한 1이 존재하기 때문입니다.

문제 해결 접근 방식

이 문제는 각 행이 정렬되어 있다는 특성을 활용하면 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 오른쪽 상단 모서리에서 출발하여 다음 규칙에 따라 이동하는 것입니다.

• 현재 위치의 값이 0이라면 → 해당 행에는 더 왼쪽에 1이 없으므로 아래로 한 칸 이동합니다.

• 현재 위치의 값이 1이라면 → 현재 열을 후보로 기록하고, 더 왼쪽에 1이 있는지 확인하기 위해 왼쪽으로 한 칸 이동합니다.

이 방식을 사용하면 시간 복잡도는 O(N + M)(N은 행 개수, M은 열 개수)이 되어, 모든 원소를 순회하는 O(N×M) 방식보다 훨씬 빠릅니다.

알고리즘 단계

• 행렬이 비어 있다면 -1을 반환합니다.

• N := 행렬의 행 개수, M := 행렬의 열 개수로 설정합니다.

• i := 0, j := M - 1 (오른쪽 상단에서 시작)

• leftmost := -1 로 초기화합니다.

• i < N 이고 j >= 0 인 동안 반복합니다.

  • matrix[i][j] 가 0이면 i := i + 1 (아래로 이동)

  • 그렇지 않으면 leftmost := j 로 기록하고 j := j - 1 (왼쪽으로 이동)

• 반복이 끝나면 leftmost를 반환합니다.

예제 코드

class Solution:
    def solve(self, matrix):
        if not matrix or not matrix[0]:
            return -1

        N = len(matrix)
        M = len(matrix[0])

        i = 0
        j = M - 1

        leftmost = -1

        while i < N and j >= 0:
            if matrix[i][j] == 0:
                i += 1
            else:
                leftmost = j
                j -= 1

        return leftmost

ob = Solution()
matrix = [
    [0, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 0, 1, 1],
    [0, 0, 1, 0]
]
print(ob.solve(matrix))

입력

[
[0, 0, 0, 1],
[0, 0, 1, 1],
[0, 0, 1, 1],
[0, 0, 1, 0] ]

출력

2

마무리

이 알고리즘은 행렬이 행 단위로 정렬되어 있다는 전제 조건 덕분에, 한 번의 탐색으로 답을 찾을 수 있습니다. 실무에서도 정렬된 데이터의 구조적 특성을 활용하면 불필요한 연산을 크게 줄일 수 있다는 좋은 예시가 됩니다. 만약 행렬이 정렬되어 있지 않다면, 각 행마다 이진 탐색(binary search)을 적용하는 방법도 고려할 수 있습니다.