10.9 정렬된 행렬 탐색

문제 

각 행과 열이 오름차순으로 정렬된 MXN 행렬이 주어졌을대, 특정한 원소를 찾는 메서드를 구현하라

 

해결법

첫번째 : 행마다 이진탐색을 할 수있다.

M개의 행이 있고 각 행을 탐색하는데 O(logN)이 걸리기 떄문에 O(MlogN)이 될 것이다.

 

두번재 해결법을 생각해보기 전에 규칙을 찾아보자

15	20	40	85
20	35	80	95
30	55	95	105
40	80	100	200

이런 행렬이 주어졌을때 55를 찾아보자. 

행의 시작점이나 열의 시작점을 보면 위치를 유추해 볼 수 있다. 열의 시작점 원소의 값이 55보다 크다면 탐색할 필요가 없고, 마찬가지로 행의 시작점 원소의 값이 55보다 크다면 탐색할 필요가 없을 것이다.

그러면 행이나 열의 마지막점에서도 똑같이 적용할 수 있다. 어떤 행이나 열의 값이 x보다 작으면 다음 행이나 열로 이동해야한다. 

- 어떤 열의 시작점 열의 원소보다 x가 크면 x는 해당 열 왼쪽에 있다. 

- 어떤 열의 마지막 원소 값이 x보다 작으면, x는 해당열 오른쪽에 있다.

- 어떤 행의 시작점 행의 원소가 x보다 크면 x는 해당 행 위쪽에 있다.

- 어떤 행의 시작점 행의 원소가 x보다 작으면 x는 해당 행 아래쪽 있다.

 

가장 큰 값을 가지는 열부터 시작해서 좌측으로 진행할 필요ㅏ 있다. 즉, 첫번째 비교대상 원소는 array[0][c-1] =85이다.

15	20	40	85
20	35	80	95
30	55	95	105
40	80	100	200

여기서 c는 열의 갯수이다. 열의 시작점 원소들을 x(55)와 비교해보면 x는 0,1,2열에 있을 수 있다는 사실을 알 수 있다.

따라서 array[0][2]에서 진행을 멈춘다.

15	20	40	85
20	35	80	95
30	55	95	105
40	80	100	200

그다음은 array[0][2]는 40으로 55보다는 작으니까 아래쪽으로 진행한다.

이런식으로 범위를 줄여가면서 정답을 찾을 수 있다.

 

def findElement(matrix, elem):
    row =0
    col =matrix[0].length -1
    while row <matrix.length and col >=0 :
        if matrix[row][col] == elem:
            return (row, col)
        elif matrix[row][col] > elem :
            col -=1
        else :
            row +=1
    return None