空놀이

1. 두개 숫자 입력 받기

1 2 

a, b = map(int, input().split())
print(a+b)

2. 한개 숫자 입력 받기

a = int(input())

https://leetcode.com/problems/climbing-stairs/

아직 이게  피보나치 수열 문제라는 것이 딱 와 닿지 않지만

일단 풀어 보았다.

class Solution:
    def climbStairs(self, n: int) -> int:
        if(n == 0):
            return 0
        if(n == 1):
            return 1
        
        dp = []
        dp.append(0)
        dp.append(1)
        dp.append(2)
        
        for i in range(3, n+1):
            dp.append(dp[i-1] + dp[i-2])
        
        return dp[n]

바이너리 서치에 대해서 배웠습니다.

생각보다 간단하네요 ㅎㅎ

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        def search(nums, target, l, r):
            while l <= r:
                m = (l+r)//2
                if nums[m] == target:
                    return m
                if nums[m] < target:
                    l = m+1
                else:
                    r = m-1
            return l
    
        return search(nums, target, 0, len(nums)-1)

바이너리 서치 잘 외웠다고 생각했는데,

중간값 계산을 while문 앞에서 해서 고생했습니다. ㅎㅎ

리스트가 비었는지 확인하는 방법은

if not matrix:

가 있는데, 이것 보다

if len(matrix) == 0:

으로 하는게 더 빠르네요 ㅎㅎ

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def BinarySearch2(target, start, end, matrix, m):
            
            while start <= end:
                n = (start + end) // 2
            
                if matrix[m][n] == target:
                    return True
                elif matrix[m][n] > target:
                    end = n-1
                elif matrix[m][n] < target:
                    start = n + 1
            return False
        
        def BinarySearch(target, start, end, matrix):
            
            while start <= end:
                m = (start + end) // 2
            
                print(start, end, m, matrix[m][0], target)
                if matrix[m][0] == target:
                    return True
                elif matrix[m][0] < target:
                    start = m + 1
                elif matrix[m][0] > target:
                    end = m - 1
                    print(end)
                
            print(start, end)
            return BinarySearch2(target, 0, len(matrix[0])-1, matrix, end)
        
        if len(matrix) == 0:
            return False
        if  len(matrix[0]) == 0:
            return False

        return BinarySearch(target, 0, len(matrix)-1, matrix)

바이너리 서치 응용 문제

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()

아이패드 프로 + 스마트 키보드로 문제 풀고 블로그에 글 올리는 중입니다.

class Solution:
    def isValid(self, s: str) -> bool:
        data = []
        for st in s:
            if(st == '(' or st == '{' or st == '['):
                data.append(st)
            elif not data:
                return False
            else:
                if(st == ')'):
                    if(data.pop() != '('):
                        return False
                elif st == ']':
                    if(data.pop() != '['):
                        return False
                elif st == '}':
                    if(data.pop() != '{'):
                        return False
        if not data:
            return True
        return False

예외처리 할 것들이 많았습니다.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ans = ""
        length = len(strs)
        
        if(length == 0):
            return ans
        elif(length == 1):
            for i in range(len(strs[0])):
                ans += strs[0][i]
        
        leng = 1000
        for i in range(length):
            if(len(strs[i]) < leng):
                leng = len(strs[i])
        

        for i in range(leng):
            for j in range(1, length):
                if(strs[0][i] == strs[j][i]):
                    if(j == length -1):
                        ans += strs[0][i]
                    else:
                        continue
                else:
                    return ans
                
        return ans