[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파
START :
[3코1파] 2023.01.04~ (297일차)
[4코1파] 2023.01.13~ (289일차)
[4코3파] 2023.10.01 ~ (27일차)
Today :
2023.10.27 [297일차]
Leetcode Binary Search 문제 (2)
[5] 33. Search in Rotated Sorted Array
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
문제 설명
오름차순으로 정렬되어 있는 배열과 target 정수가 주어진다.
해당 배열을 rotate (회전) 한 후 target 정수를 O(logN)으로 찾고, 해당 인덱스를 return 하고 target이 없으면 -1을 리턴한다.
문제 풀이 방법
사실 이거 아직 이해가 된다.
내 코드
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)-1
while l<=r:
mid = (l+r)//2
if target == nums[mid]:
return mid
if nums[l] <= nums[mid]:
if nums[l] < target or nums[mid] < target:
l = mid+1
else:
r = mid-1
else:
if nums[r] < target or nums[mid] < target:
r = mid-1
else:
l = mid+1
return -1[6] 981. Time Based Key-Value Store
https://leetcode.com/problems/time-based-key-value-store/description/
문제 설명
서로 다른 타임스탬프에서 동일한 키에 대한 여러 값을 저장할 수 있고,
특정 타임스탬프에서 저장된 키 값을 검색할 수 있는 시간 기반 key-value 데이터 구조인 TimeMap 클래스를 구현하는 문제이다.
- TimeMap() 메소드는 데이터 구조의 객체를 초기화한다.
- void set(String key, String value, int timestamp) 주어진 타임스탬프의 값 값과 함께 키 키를 저장한다.
- String get(String key, int timestamp) timestamp_prev <= timestamp를 사용하여 이전에 set이 호출된 값을 반환한다. 값이 여러 개인 경우 가장 큰 timestamp_prev와 관련된 값을 반환한다. 값이 없으면 ""를 반환한다.
문제 풀이 방법
타임스탬프 객체는 딕셔너리 구조로 초기화한다.
그외에 저장하는 set 메소드는, key 값에 해당하는 여러 값과 타임 스탬프가 저장될 수 있도록 value로 리스트를 선언한다.
그 뒤에 set 메소드로, 값이 여러개인 경우 가장 큰 인자로 들어온 timestamp와 가장 가까운 이전 timestamp (timestamp_prev)를 반환하기 위해서, 해당 타임스탬프를 찾을 때 binary search를 이용해 가져오도록 한다.
내 코드
class TimeMap:
def __init__(self):
self.store = {}
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.store:
self.store[key] = []
self.store[key].append([value, timestamp])
def get(self, key: str, timestamp: int) -> str:
ans = ''
values = self.store.get(key, [])
l,r = 0, len(values)-1
while l <=r:
mid = (l+r)//2
if values[mid][1] <= timestamp:
ans = values[mid][0]
l = mid+1
else:
r = mid-1
return ans
이거는 이해된다.
[7] 4. Median of Two Sorted Arrays
문제 설명
두 개의 오름차순 배열이 주어진다.
두 배열의 크기는 일정하지 않다.
두 배열을 합쳤을 때, 중앙값을 구하라
O(log(m+n)) 의 시간복잡도로~!
문제 풀이 방법
그냥 배열 두개 합쳐서 sort 해서 median 구하면 안되냐고요
빡빡하게 구시네 증말..
내 코드
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
A, B = nums1, nums2
total = len(nums1) + len(nums2)
half = total // 2
if len(B) < len(A):
A, B = B, A
left, right= 0, len(A) - 1
while True:
i = (left + right) // 2
j = half - i - 2
Aleft = A[i] if i >= 0 else float("-infinity")
Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
Bleft = B[j] if j >= 0 else float("-infinity")
Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")
if Aleft <= Bright and Bleft <= Aright:
# odd
if total % 2:
return min(Aright, Bright)
# even
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
elif Aleft > Bright:
right = i - 1
else:
left = i + 1이것도 아직 이해가 안된다..?
여담
binary search hard 문제 미친거같다.
binary search 2문제 지금 이해 안됨
클남 어캄? 다시 봐야지 뭘 어쩜
근데 오늘은 슬라이딩 윈도우도 해야됨
큰일남
