24-06-22 알고리즘 문제 풀이

오늘은 주말이라 추가로 많은 것을 학습하기 보다는 공부해왔던 것을 조금 정리해보는 시간을 주로 가졌던 것 같다. 내일부터는 개인 과제로 주어진 것을 본격적으로 시작할 생각이다.

 

여기에는 오늘 풀어본 간단한 알고리즘 문제를 하나 정리해본다.

 

 

1. 알고리즘 문제 풀이

오늘은 leetcode에 있는 '240. Search a 2D Matrix II' 문제를 풀어보았다. 

1-1. 풀어본 문제

[문제]

 

m×n 정수 행렬인 matrix 에서 값 target을 찾는 효율적인 알고리즘을 작성하세요. 이 행렬은 다음과 같은 특징을 가집니다.

 

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

- 예시 1

입력: matrix = [[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]], target = 5

출력: true

 

- 예시 2:

입력: matrix = [[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]], target = 20

출력: false

 

- 제한 사항

• m == matrix.length
• n == matrix[i].length
• $1 {\;}{\leq}{\;} n, {\;} m {\;}{\leq}{\;} 300 $
• $ -10^{9} {\;}{\leq}{\;} matrix[i][j] {\;}{\leq}{\;} 10^{9} $
• 각 행의 모든 정수는 오름차순으로 정렬되어 있다.
• 각 열의 모든 정수는 오름차순으로 정렬되어 있다.
• $ -10^{9} {\;}{\leq}{\;} target {\;}{\leq}{\;} 10^{9} $

 

1-2. 문제 풀이

먼저 어떻게 해야 가장 효율적으로 원하는 값을 찾아낼 수 있을지에 대해 고민을 해보아야 했다. 어느 부분을 시작점으로 잡아야할지 부터가 고민이 필요했다.

 

곰곰히 생각해본 결과 내린 결론은 첫 번째 행의 마지막 열을 시작점으로 잡고 원하는 값을 찾아나가는 것이 생각해낼 수 있는 가장 좋은 시작점이었다.

 

 

다음 그림에서 첫 번째 행의 4번째 열인 11번의 값과 타겟의 값을 비교한다고 생각해보자. 만약 타겟이 11보다 작다면 11 보다 큰 값의 행과 열은 앞으로 찾아보지 않아도 된다.(행과 열이 오름차순으로 정렬되어있기 때문에) 다시 말해 7로 이동한 뒤에 다시 값을 찾아나가면 된다. 반면 11보다 타겟의 값이 크다면 같은 행에 있는 더 작은 수의 열들에 대해서는 확인이 필요하지 않지만 그 보다 큰 값을 가지는 모든 행과 열을 다 뒤져보아야 한다.

 

하지만 첫 번째 행의 마지막열인 15부터 출발을 한다고 생각해보자. 타겟이 값이 15보다 작다면 이제 마지막 열에 해당하는 값들은 체크해보지 않아도 된다.(해당 열의 나머지 값들은 모두 15보다 크기 때문에) 그리고 타겟의 값이 15보다 크다면 행의 크기를 1 증가시킨 뒤 다시 값을 찾아나가면 된다. (같은 행에는 15보다 큰 값이 없으므로)

 

위와 같은 사실들을 이용하여 직접 코드를 작성해 보았다.

 

class Solution {
    fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
        var answer = false
        
        // 시작점은 첫 행의 마지막 열
        var row = 0
        var col = matrix[0].size - 1

        while (true) {
            // 행과 열이 행렬의 범위를 벗어나면 break
            if (row >= matrix.size || col < 0 ) break
        
            when {
                // 타겟 값을 찾으면 true를 반환
                matrix[row][col] == target -> {answer = true; break}
                
                // 타겟 값보다 크면 왼쪽 열로 이동
                matrix[row][col] > target -> col--
                
                // 타겟 값보다 작으면 아래행으로 이동
                else -> row++
            }
        }
        
        return answer
    }
}

위와 같이 코드를 작성하면 답안으로 잘 통과된다.

 

문제 해결을 위한 아이디어를 떠올리는 시간이 조금 필요했는데, 시작점을 잘 정하고나니 그 뒤로는 쉽게 문제가 풀렸던 것 같다.

 

2. 오늘 배운 것

- 이번 주에 배웠던 JPA와 네트워크 관련 지식을 한 번도 복습해보는 시간을 가졌다.

- JPA를 능숙하게 다룰 수 있도록 연습이 많이 필요할 것 같다.