bright

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        table = {
            ')': '(',
            '}': '{',
            ']': '[',
        }
        
        for i in s:
            if i not in table:
                stack.append(i)
            elif not stack or table[i] != stack.pop():
                return False 
            
        return len(stack) == 0 

입력된 괄호 식이 올바른지 판단하는 문제. 

테이블에 없는 값이 들어오면 스택에 넣고 있는 값이 들어오면 스택에서 꺼내서 값이 맞는지 확인한다. 

딕셔너리 자료형을 활용해서 풀이한다. 

leetcode.com/problems/valid-parentheses/

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        def dfs(x,y):
            if x < 0 or y < 0 or x>= len(grid) or y>= len(grid[0]) : 
                return False 
            
            if grid[x][y] == "1" :
                grid[x][y] = 0 
                
                dfs(x-1,y)
                dfs(x+1,y)
                dfs(x,y+1)
                dfs(x,y-1)
                
                return True
            return False 
        
        cnt = 0 
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if dfs(x,y) == True:
                    cnt += 1 
        return cnt

음료수 얼려 먹기 문제와 거의 유사한 dfs 문제이다. 

입력 받는 방식이 조금 특이하다. 

Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

leetcode.com/problems/number-of-islands/

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0 
        
        for i in range(len(prices)-1):
            if prices[i] < prices[i+1]:
                result += prices[i+1] - prices[i]
                
        return result 

쌀 때 사서 비쌀 때 팔아 가장 높은 수익을 얻는 문제.

그리디 알고리즘을 사용하여 풀면 간단하다. 

만약, 현재보다 다음 값이 오른다면 사고 판다. 

leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

팰린드롬 : 앞 뒤가 똑같은 문자열. 

주어진 문자열이 팰린드롬인지 확인할 것. 대소문자 구분 x 영문자와 숫자만을 취급. 

ex ) 

INPUT = "A man, a plan, a canal: Panama"  

OUTPUT = True

INPUT = "0P"
OUTPUT = False 

class Solution:
    def isPalindrome(self, s: str) -> bool:
        real_s = []
        for i in s : 
            if 48<=ord(i)<=57 or 65<= ord(i) <=90 or 97<=ord(i)<=122 :
                real_s.append(i)
        
        for i in range( len(real_s)//2 ):
            if real_s[i].upper() != real_s[ len(real_s)-i-1 ].upper():
                return False 
        return True

tip!  

real_s.append(i)  할 때, real_s.append( i.upper() ) 로 리스트에 추가하면 더 효율적으로 코드를 작성할 수 있다. 

leetcode.com/problems/valid-palindrome/