[Mock] Google 15

278. First Bad Version

https://leetcode.com/problems/first-bad-version/

My Answer 1: Accepted (Runtime: 32 ms - 54.01% / Memory Usage: 14.3 MB - 44.29%)

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l = 1
        r = n
        while l <= r:
            m = (l+r) // 2
            if isBadVersion(m):
                r = m - 1
            else:
                l = m + 1
                
        return l

그냥 for 문으로 돌렸더니 타임리밋이길래 Binary Search 로 하니까 통과~

---

1146. Snapshot Array

https://leetcode.com/problems/snapshot-array/

My Answer 1: Time Limit Exceeded (69 / 71 test cases passed.)

class SnapshotArray:

    def __init__(self, length: int):
        self.array = [0] * length
        self.snaps = []
        self.snap_id = -1

    def set(self, index: int, val: int) -> None:
        self.array[index] = val

    def snap(self) -> int:
        self.snaps.append(self.array[:])
        self.snap_id += 1
        return self.snap_id

    def get(self, index: int, snap_id: int) -> int:
        return self.snaps[snap_id][index]


# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)

init)
array => length 길이의 리스트
snaps => snap 할 때마다 그때의 리스트 저장
snap_id => -1 부터

set)
array[index] 값 변경

snap)
snap 할 때마다 array 복사해서 snaps 에 넣어주고 id + 1

get)
snap_id 번째 index 값 가져오기

snap 할 때를 바꿔야할 거 같아서
dictionary 에 [val, snap_id] 식으로도 해봤는데..

안됨...

Solution 1: Accepted (Runtime: 480 ms - 53.51% / Memory Usage: 46.5 MB - 36.98%)

class SnapshotArray:

    def __init__(self, length: int):
        self.A = [[[-1, 0]] for _ in range(length)]
        self.snap_id = 0

    def set(self, index: int, val: int) -> None:
        self.A[index].append([self.snap_id, val])

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        i = bisect.bisect(self.A[index], [snap_id + 1]) - 1
        return self.A[index][i][1]


# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)

이것도 Binary Search 로 한다니 놀랍네요..

snap 도 array 전체를 snap 할 필요가 X

i = bisect.bisect(self.A[index], [snap_id + 1]) - 1
=> snap_id + 1 의 위치를 찾아서 바로 앞 (-1) 의 인덱스 가져오기

bisect 함수

정렬된 리스트에서
bisect_left(a, x) : 리스트 a 에 값 x 를 삽입할 가장 왼쪽 인덱스
bisect_right(a, x) : 리스트 a 에 값 x 를 삽입할 가장 오른쪽 인덱스
bisect(a, x) : bisect_left 와 유사, 우측으로 삽입되는 인덱스