7/3 코테일지 (2D binary search, dictionary 키 값에 대한 접근)
2D Binary Search
NeetCode (https://neetcode.io/problems/search-2d-matrix)
내 코드
밑의 코드를 작성하였는데 시간 초과가 떳다. 답안 코드와 동일하게 O(log(mn))의 시간 복잡도를 가지는 코드이지만 시간 초과가 뜬다.
알고리즘을 간단히 설명하자면 먼저 row를 선택하는 알고리즘에서는 target보다 작은 첫 번째 요소를 가진 row 중 가장 높은 row를 선택하는 것이다. 그러한 row가 선택되면 그 row에 대한 binary search를 한번 더 실시한다.
이러한 과정에서 while문 안에서 각 각의 조건문이 실행될 때 R = mid, L = mid를 해주게 되었는데 그 이유는 기존의 방식대로 binary search를 하면 mid가 target보다 큰 값 또는 작은 값의 index를 가질 수 있기 때문에 위의 첫 번째 row를 선택할 때 문제가 생긴다. 따라서 R = mid, L= mid를 해줌으로써 mid가 항상 target보다 작은 첫 번째 요소를 가지는 row를 가지게끔 하였다. 따라서 반으로 나눌 때 mid가 계속해서 중복으로 포함되어서 코드의 효율성이 떨어진다.
두 번재 문제는 바로 해당하는 row가 없을 때 바로 false를 return 해주지 못하기 때문이다. 만약 선택한 row가 [1,2,7,10]인데 target이 5이면 바로 return false를 해주지 못하고 해당하는 row에 binary search를 함으로써 또한 코드의 실행시간이 길어진다.
class Solution:
def searchMatrix(self, matrix, target):
m = len(matrix)
n = len(matrix[0])
# Find the potential row where the target could be located
L, R = 0, m - 1
while L <= R:
if R - L != 1:
mid = (L + R) // 2
if matrix[mid][0] > target:
R = mid
elif matrix[mid][0] < target:
L = mid
else:
return True
else:
if matrix[R][0] > target:
row = L
else:
row = R
break
# If the target is the first element of the found row
if matrix[row][0] == target:
return True
# Perform binary search in the identified row
L, R = 0, n - 1
while L <= R:
mid = (L + R) // 2
if matrix[row][mid] > target:
R = mid - 1
elif matrix[row][mid] < target:
L = mid + 1
else:
return True
# Target not found
return False
답안 코드
답안 코드는 위의 문제점을 각 row의 첫 번째 요소만 비교하는 것이 아닌 각 row의 첫 번째 요소와 마지막 요소를 target과 비교를 함으로써 해결한다. 따라서, 첫 번째 binary search가 끝났을 때, mid의 값은 항상 target을 포함하는 row이다. 그렇지 않으면 바로 false를 return 해준다. 내 코드의 두 가지 문제를 모두 해결했다는 것을 알 수 있다.
class Solution:
def searchMatrix(self, matrix, target):
m= len(matrix)
n= len(matrix[0])
#row 값 찾기
row = 0
L, R = 0, m - 1
while (L<=R) :
mid = int((L+R)/2)
if matrix[mid][-1] < target:
L = mid + 1
elif matrix[mid][0] > target:
R = mid - 1
else :
break
if not (L<=R):
return False
row = mid
L, R = 0, n - 1
while (L<=R) :
mid = int((L+R)/2)
if matrix[row][mid] > target:
R= mid - 1
elif matrix[row][mid] < target:
L = mid + 1
else:
return True
return False
10816 숫자 카드 2
처음에는 밑에와 같이 binary search로 해당하는 값 하나를 찾고 양 옆으로 포인터를 옮겨가며 총 몇개인지를 구하는 방법을 사용했다. 처음부터 하나씩 보는 알고리즘보다는 낫겠지만 어차피 하나씩 옮겨가며 확인하는 것이다 보니 시간초과가 떳다.
import sys
n = int(sys.stdin.readline().rstrip())
n_array = list(map(int,(sys.stdin.readline().rstrip().split(' '))))
m = int(sys.stdin.readline().rstrip())
m_array = list(map(int,(sys.stdin.readline().rstrip().split(' '))))
n_array.sort()
def binarySearch(array, target):
L, R = 0, len(array)-1
while (L<=R):
mid = int((L+R)/2)
if target > array[mid] :
L = mid + 1
elif target < array[mid] :
R = mid - 1
else :
return mid
return -1
ans = []
for m in m_array:
l = 0
r = 0
mid = binarySearch(n_array,m)
if mid == -1 :
ans.append(0)
else :
while mid + r <= len(n_array) -1 and n_array[mid + r] == m:
r += 1
while mid - l >= 0 and n_array[mid - l] == m:
l += 1
ans.append(l+r-1)
print(*ans)
다음은 될까 해서 해본 counting sort 알고리즘을 활용하여 해봤는데 실제로 성공하였다. 메모리 낭비가 큰 단점이 있을 거 같다.
import sys
n = int(sys.stdin.readline().rstrip())
n_array = list(map(int,(sys.stdin.readline().rstrip().split(' '))))
m = int(sys.stdin.readline().rstrip())
m_array = list(map(int,(sys.stdin.readline().rstrip().split(' '))))
array = [0 for _ in range(20000002)]
for n in n_array :
array[n] += 1
for m in m_array:
print(array[m], end= " ")
다음은 답안 코드에서 본 코드다. 위의 알고리즘과 비슷하지만, dictionary를 통해서 메모리 낭비를 줄였다. 처음에는 dictionary를 활용해볼까 하는 생각이 있었지만 dictionary의 경우 배열의 시작 주소에 index를 더한 값으로 원하는 배열의 특정 인덱스에 O(1)으로 접근 가능한 배열과 다르게 key 값에 대한 접근을 할 때 시간 복잡도가 O(1)이 아니라고 생각하였다. 하지만 알고보니, dictionary 자료형 또한 키 값에 대한 접근이 O(1)이며 이것은 딕셔너리가 해쉬 테이블이라는 자료구조를 활용하기 때문이다.
n = int(input())
n_list = sorted(list(map(int, input().split())))
m = int(input())
m_list = list(map(int, input().split()))
m_dict = {key:0 for key in m_list}
for i in n_list:
if i in m_dict:
m_dict[i] += 1
for key in m_list:
print(m_dict[key], end=' ')