leetcode 653(2SUM4), 946(stack), 729(이진 탐색), 722(정규식 regex)

653 https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

https://qkqhxla1.tistory.com/1055 여기서 1번, 167번의 2 sum을 풀었었는데 이번엔 단순히 트리에서 검색하는거다.

검색부만 트리로 변경한다.

from collections import deque

class Solution(object):
    def findTarget(self, root, target):
        queue = deque([root])
        d = set()
        while queue:
            node = queue.popleft()
            if target - node.val in d:
                return True
            d.add(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return False

946 https://leetcode.com/problems/validate-stack-sequences/

stack의 push pop동작을 했을때 pop처럼 결과가 나올수 있는지를 묻는 문제이다. 직접 스택에 넣어보면서 풀면 된다.

from collections import deque

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        stack = deque()
        for p in pushed:
            stack.append(p)
            while stack and stack[-1] == popped[0]:
                stack.pop()
                popped.pop(0)
        
        return len(stack) == 0

729 https://leetcode.com/problems/my-calendar-i/

문제를 보면 예약 날짜를 입력받는데 그게 이전에 입력한 예약 날짜와 겹치면 False를 리턴해야 한다. 근데 예약 날짜의 범위가 0~10**9이므로 엄청 크다. 처음엔 실제로 시작날짜와 끝날짜를 리스트로 만들어서 예약된 날은 1로, 아닌 날은 0으로 해볼까 했는데 날짜 범위가 너무 커서 이건 이진 탐색 트리로 구현했다.

from collections import deque

class MyCalendar(object):
    def __init__(self):
        self.binary_search_tree = {}
        self.root = None
# 
    def book(self, start, end):
        if not self.binary_search_tree:
            self.binary_search_tree[start] = [[start, end], None, None]  # value, left, right
            self.root = start
        else:
            node = self.binary_search_tree[self.root]  # 루트부터 시작해서 탐색함.
            while node:
                if end <= node[0][0]:
                    if not node[1] and node[1] != 0:
                        node[1] = start
                        self.binary_search_tree[start] = [[start, end], None, None]
                        break
                    else:
                        node = self.binary_search_tree[node[1]]
                elif node[0][1] <= start:
                    if not node[2] and node[2] != 0:
                        node[2] = start
                        self.binary_search_tree[start] = [[start, end], None, None]
                        break
                    else:
                        node = self.binary_search_tree[node[2]]
                else:
                    return False
        return True

722 https://leetcode.com/problems/remove-comments/

정규식으로 풀었는데 훨씬 깔끔한 답이 있어 올린다...

https://leetcode.com/problems/remove-comments/discuss/109195/1-liners

def removeComments(self, source):
    return filter(None, re.sub('//.*|/\*(.|\n)*?\*/', '', '\n'.join(source)).split('\n'))

//.*     # matches single line comments
|        # 'or' operator
/\*      # matches '/*',
(.|\n)*? # matches everything(including '\n') inside block comment 
         # question mark will make regex '(.|\n)*' non-greedy or lazy
\*/      # matches '*/'