matrix_Leetcode_240. Search a 2D Matrix II

https://leetcode.com/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked

 

문제접근

아이디어1

1. 주어진 매트릭스는 x,y가 증가하는 방향으로 이동하면 해당 index의 value가 증가한다.
2. 다만, (3,1)의 값이 (2,3) 보다 항상 크지 않다. 대소 비교는 각 행, 열 마다 개별적이다.
3. bfs를 이용하여 조건에 맞는 index가 존재하는지 찾는다.

아이디어2

1. 행 렬을 꼭 이동하지 않고, 그리디에 가깝게  풀어보기?

 

정답코드

아이디어 1을 사용하여 정답을 맞춘 코드

그런데, 129msBeats5.56% 로 성능이 좋지는 않다.

class Solution {
    struct Point: Hashable {
        let x: Int
        let y: Int
    }

    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        /// (x,y)
        let moves = [(1,0), (0,1)] 
        var queue = [Point]()
        // var visited = [Point]()
        var visited = Set<Point>()
        var sol = false

        let maxY = matrix.count
        let maxX = matrix[0].count

        queue.append(Point(x: 0, y: 0))

        while !queue.isEmpty {
            let targetPoint = queue.removeFirst()
            // guard !visited.contains(targetPoint) else { continue }
            // visited.append(targetPoint)
            guard visited.insert(targetPoint).inserted else { continue }

            let value = matrix[targetPoint.y][targetPoint.x]
            if value == target {
                sol = true
                break
            }
            
            for move in moves {
                let nextX = targetPoint.x + move.0
                let nextY = targetPoint.y + move.1
                guard nextX < maxX && nextY < maxY else { continue }
                queue.append(Point(x:nextX, y: nextY))
            }
        }
        
        return sol
    }
}

개선코드

queue를 버리고, Backtracking에 가깝게 구현

99msBeats25.93%

유의미하게 나아졌지만? 아직 하위 25%이므로 좋은 코드가 아니다.

class Solution {
    struct Point: Hashable {
        let x: Int
        let y: Int
    }

    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        let maxY = matrix.count
        let maxX = matrix[0].count
        
        for y in 0..<maxY {
            for x in 0..<maxX {
                let value = matrix[y][x]
                if value == target {
                    return true
                } else if value > target {
                    break
                }
            }
        }

        return false
    }
}

모범코드

한끝차이로 코드의 의도와 성능이 갈린다.

아래 코드는 83ms.

matrix의 col을 뒤쪽부터 시작한다

해당 코드의 의도는 이분탐색에 가까운 형태로 탐색하기 위해서이다.

matrix[0][0], 즉 작은 값부터 탐색을 시작하면, 갈 수 있는 두 방향 모두 더 큰값이므로 양 쪽 다 탐색해야한다.

하지만 column의 뒤쪽부터 시작하면 기준이 달라진다.

value가 target보다 크면, column의 인덱스를 줄여 더 작은 값을 찾을 수 있다.

value가 target보다 작으면 row의 인덱스를 증가시켜 더 큰값을 찾을 수 있다.

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        let m = matrix.count
        let n = matrix[0].count
        var i = 0
        var j = n - 1

        while i < m && j >= 0 {
            if matrix[i][j] == target {
                return true
            } else if matrix[i][j] < target {
                i += 1
            } else {
                j -= 1
            }
        }
        
        return false
    }
}