-
99클럽(2기) - 코테스터디 14일차 TIL # Binary SearchAlgorithm 2024. 6. 11. 20:42
LeetCode - 1351. Count Negative Numbers in a Sorted Matrix
Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.
- Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 100
- -100 <= grid[i][j] <= 100
1. 첫 번째 풀이
풀이는 20분 정도 걸렸지만이중 반복문으로 모든 행과 열을 순회하기 때문에 시간 복잡도가 O(m * n)이다. 모든 행은 다 탐색하더라도 열에 대해서는 이분 탐색을 적용할 수 있을 것 같았지만 해결책이 쉽게 떠오르지 않았다.
1) 행렬 순회를 위해 행의 인덱스와 열의 인덱스 초기화
행의 인덱스 m을 행의 개수로, 열의 인덱스 n을 첫 번째 행의 열의 개수로 초기화해준다. m * n 행렬이므로 첫 번째 행의 열의 개수는 각각의 모든 행의 열의 개수와 동일하다. 행렬을 순회할 때, range(m)과 range(n)과 같이 행과 열의 인덱스를 이용할 것이고 range(n)은 0부터 n-1까지의 범위를 의미하므로 n과 m에 1을 빼지 않고 그대로 사용했다.
2) 모든 행에 대한 모든 열을 순회
2-1) 첫 번째 열이 음수인 경우
하나의 행에 대해서 첫 번째 열이 음수인 경우 그 뒤는 볼 것도 없으므로 정답에 모든 열의 개수를 더해준다.
2-2) 첫 번째 열이 음수가 아닌 경우
하나의 행에 대해서 첫 번째 열이 음수가 아닌 경우 음수가 나올 때까지 순회하다가 음수인 열이 나오면 정답에 '모든 열의 개수에서 음수인 열을 만나기까지 한 칸 오른쪽으로 간 횟수를 빼준 값'을 더해준다.
class Solution: def countNegatives(self, grid: List[List[int]]) -> int: answer = 0 m = len(grid) # 행의 개수 n = len(grid[0]) # 첫 번째 행에 대한 열의 개수 (= 모든 행의 열의 개수) for i in range(m): # 모든 행에 대해서 if grid[i][0] < 0: # 첫 번째 열이 음수면 answer += n # 정답에 모든 열의 개수를 더해준다 else: for j in range(n): # 모든 열에 대해서 if grid[i][j] < 0: # 음수인 열이 나오면 answer += n - j # 정답에 '모든 열의 개수에서 음수인 열을 만나기까지 진행한 횟수를 빼준 값'을 더해준다 break return answer
2. 두 번째 풀이
오늘도... 나의 쓰앵님 챗지피티에게 도움을 받아 시간 복잡도 O(m + n)으로 개선했다. 행은 맨 마지막에서 맨 첫 번째 방향으로 진행하고, 열은 첫 번째에서 맨 마지막 방향으로 진행해서 대각선 방향으로 만나게 했다. row는 시작 시 m - 1이고 최종적으로 0까지 감소할 수 있어 m번 감소하며, col은 시작 시 0이고 최종적으로 n - 1까지 증가할 수 있어 총 n번 증가할 수 있다. 그런데 각 반복에서 m이나 n 중 하나만 변하기 때문에 전체 시간복잡도는 O(m + n)이 된다.
1) 행렬 순회를 위해 행의 인덱스와 열의 인덱스, 행의 개수와 열의 개수 초기화
행의 개수와 열의 개수는 행렬 순회 시 while문의 조건으로 사용하기 위함이고, 행의 인덱스와 열의 인덱스는 행렬에 해당 인덱스로 접근하기 위해서 사용한다.
2) 현재 열이 음수인지 여부에 따라서 행 이동 또는 열 이동
행의 인덱스가 0보다 크고 열의 인덱스가 열의 개수보다 작을 때까지만 아래 로직 반복
2-1) 현재 열이 음수인 경우(행의 진행 방향: 맨 마지막 행 → 맨 첫 번째 행)
현재 행의 현재 열의 위치가 음수라면 이후의 열은 모두 음수이기 때문에 이 때부터 다음 열을 탐색할 필요가 없다. 정답에 '전체 열의 갯수에서 현재 열의 인덱스를 빼준 만큼' 더한 후 한 칸 위의 행을 탐색하기 위해 행의 인덱스에서 1을 빼준다.
2-2) 현재 열이 음수가 아닌 경우(열의 진행 방향: 맨 첫번째 열 → 맨 마지막 열)
현재 행의 현재 열의 위치가 음수가 아니라면 다음 열로 이동해서 음수인지 확인해야 하기 때문에 열의 인덱스에 1을 더해준다.
class Solution: def countNegatives(self, grid: List[List[int]]) -> int: m = len(grid) # 행의 개수 n = len(grid[0]) # 첫 번째 행에 대한 열의 개수 (= 모든 행에 대한 열의 개수) answer = 0 row = m - 1 # 행의 인덱스를 맨 마지막으로 초기화 col = 0 # 열의 인덱스를 맨 첫 번째로 초기화 while col < n and row >= 0: if grid[row][col] < 0: # 현재 행에 대한 현재 열의 위치가 음수라면 answer += (m - col) # 정답에 '전체 열의 갯수에서 현재 열의 인덱스를 빼준 만큼' 더함 row -= 1 # 행을 한 칸 위로 이동 else: # 음수가 나올 때까지 한 칸 오른쪽으로 이동 col += 1 return answer
3. 느낀점
시간복잡도 개념이 왜 중요한지 느껴진다. 로직 개선의 기준이 된달까,, 왜 첫 번째 떠오르는 생각은 항상 시간복잡도가 높은 풀이일까.. 오늘 두번째 풀이를 하면서 행렬 순회의 방향을 바꾸는 것 만으로도 시간복잡도가 O(m * n)에서 O(m + n)으로 줄어드는 것을 경험하며, 복잡한 것을 간단하게 추상화하는 포인트는 간단하면서도 떠올리기 어렵다고 느꼈다. 또, 이러한 능력이 진짜 실력이 아닐까라는 생각을 요즘 참 많이 하게 된다.
'Algorithm' 카테고리의 다른 글
99클럽(2기) - 코테스터디 16일차 TIL # Graph (0) 2024.06.13 99클럽(2기) - 코테스터디 15일차 TIL # Graph (0) 2024.06.12 99클럽(2기) - 코테스터디 13일차 TIL # Binary Search (1) 2024.06.11 99클럽(2기) - 코테스터디 12일차 TIL # Dynamic Programming (0) 2024.06.10 99클럽(2기) - 코테스터디 11일차 TIL # Dynamic Programming (1) 2024.06.07 - Constraints: