리트코드 74. Search a 2D Matrix JAVA

문제

문제 해석

1. 배열은 int[m][n]으로 주어져 있다. -> 모든 행의 길이가 같다.
2. 배열은 오름차순으로 주어져있다.

이 때 O(log(m*n))의 시간 복잡도를 가지는 코드를 구현해라

이 문제의 핵심은 2차 배열을 쭉 늘려서 1차 배열처럼 생각하고 문제를 푸는 것이다.

문제의 킥

위의 사진은 2차원 배열을 1차원처럼 늘려쓴 것이다.
CN[3] -> N[0][3]으로

CN[4] -> N[1][0]으로

CN[7] -> N[1][3]으로

CN[8] -> N[1][0]으로

CN[9] -> N[0][3]으로

매핑된다.

이를 통해 볼 떄 CN의 길이를 N의 ROW로 나눈 몫이 N의 행, 나머지가 N의 열이된다는 것을 알 수 있다.

이렇게 2차원배열을 1차원 배열처럼 사용할 수 있게 되면 그 이후는 간단하게 이진 검색알고리즘을 이용하기만 하면 된다.

수도 코드

 end(1차원 배열 전체 길이) = 행(m) * 열(n) - 1
 start = 0

 while(start <= end)
     mid = start + (end - start /2)

    2차원 배열로 변경해서 값을 확인해야된다.
    if(n[mid/n[0].length][mid%n[0].length] < target)
        start = mid + 1;
    else if(n[mid/n[0].length][mid%n[0].length] > target)
        end = mid - 1;
    else
        return true;  

2차원 배열을 1차원 배열처럼 사용할 수 있다면 나머지는 이진 검색 알고리즘을 활용하기만 하면된다.

코드

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        return binarySearch(matrix,target);
    }

    public boolean binarySearch(int[][] n , int target){
        int start = 0;
        int end = (n.length * n[0].length) - 1;

        while(start <= end){
            int mid = start + (end - start)/2;

            if(n[mid/n[0].length][mid%n[0].length] < target)
                start = mid + 1;
            else if(n[mid/n[0].length][mid%n[0].length] > target)
                end = mid - 1;
            else
                return true;          
        }
        return false;
    }
}

코드의 설명은 위의 수도코드에서 한 것 처럼 2차원 배열을 1차원 배열처럼 만들어서 검사 -> 2차원 배열로 값을 검증 하는 구조다.

회고

어디 문제를 풀때 였는지 기억은 나지 않지만 2차원 배열을 1차원 배열로 변경해서 문제를 푸는 문제가 있었는데 그 문제를 풀 때 처럼 2차원 배열을 1차원 배열로 해서 문제를 풀었더니 쉽게 나머지는 쉽게 해결할 수 있었다.
코딩도 결국 다양한 문제를 접해보고 직접 풀어봐야된다는 것을 플로이드의 토끼와 거북이 알고리즘에 이어 다시한번 생각해보는 계기가 되었다.

2차원 배열을 1차원 배열처럼만 생각할 수 있다면 비교적 쉽게 접근할 수 있는 문제가 아닌가 싶다.

다른 사람 문제 풀이

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for(int i = 0 ; i < matrix.length ; i++) {
            for(int j = 0 ; j < matrix[0].length ; j++) {
                if(matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

단순하게 2중 for문을 이용해서 문제를 풀었다.
위의 방식은 O(m*n)의 시간 복잡도를 가질 것으로 예상된다.