空놀이

바이너리 서치 응용 문제

class Solution:
    def mySqrt(self, x: int) -> int:
        def BinarySearch(start, end, x):
            while start <= end:
                m = (start + end) // 2
                if m * m == x:
                    return m
                elif m * m < x:
                    start = m +1
                elif m * m > x:
                    end = m -1
            return end
        return BinarySearch(0, x, x)

이렇게 풀면 엄청 느릴 것 같지만...

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        data = []
        for i in range(len(matrix[0])):
            for j in range(len(matrix)):
                data.append(matrix[i][j])
            
        data.sort()
        
        return data[k-1]
        

Stack을 만드는 건데 list를 사용해서 만들었더니 느리다.

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.data = []
        
    def push(self, x: int) -> None:
        self.data.append(x)
        
    def pop(self) -> None:
        if not self.data:
            return
        
        self.data.pop()

    def top(self) -> int:
        if not self.data:
            return []
        return self.data[len(self.data)-1]

    def getMin(self) -> int:
        if not self.data:
            return []
        return min(self.data)    


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()