leetcode 224(basic calculator), 88(merge sorted list), 981(이분 탐색), 127(bfs, word ladder)

224 https://leetcode.com/problems/basic-calculator/

코드가 너무 더럽고 효율도 낮다.. ㅠㅠ 접어놓음.

from collections import deque

class Solution(object):
    def calculate(self, s):
        #s = "(5-(1+(5)))"
        stack = deque()
        len_s = len(s)
        
        i = 0
        while i < len_s:
            if len(stack) > 1 and stack[-2] in ['-', '+'] and (stack[-1].isdigit() or (stack[-1][0] == '-' and stack[-1][1:].isdigit())):
                cur_int = int(stack.pop())
                sign = stack.pop()
                prev_int = int(stack.pop())
                ans = prev_int + cur_int if sign == '+' else prev_int - cur_int
                stack.append(str(ans))
                continue
            elif s[i] in ['-', '+', '(', ')']:
                if s[i] == ')':
                    n = int(stack.pop())
                    stack.pop()
                    si = 1
                    if stack:
                        sign = stack.pop()
                        si = 1 if sign == '+' else -1
                        stack.append('+')
                    stack.append(str(si*n))
                else:
                    stack.append(s[i])
            elif s[i].isdigit():
                j = i
                while j < len_s and s[j].isdigit():
                    j += 1
                stack.append(s[i:j])
                i = j
                continue
            i += 1
        if len(stack) == 3:
            return int(stack[0]) + int(stack[2]) if stack[1] == '+' else int(stack[0]) - int(stack[2])
        return stack[0]

모범 답안을 붙여놓음.

from collections import deque

class Solution(object):
    def calculate(self, s):
        #s = "(1+(4+5+2)-3)+(6+8)"
        stack = deque()
        num, res, sign = 0, 0, 1 
        for c in s:
            if c.isdigit():
                num = num * 10 + (ord(c) - ord('0'))  # 이런식으로 숫자가 반복될경우에 값을 누적함. 좋은 방법이다...
            elif c in ['-', '+']:
                res += num * sign  # sign 은 만약 1+2라고 하면 +1+2라고 하고 푸는게 된다.(sign의 초기값이 1이므로) sign이 현재 num이전에 있던 +나 -를 알려준다.
                num = 0
                sign = 1 if c=='+' else -1
            elif c == '(':  # 여는 괄호가 나오면 중간 결과값과 sign을 스택에 누적해놓는다.
                stack.append(res)
                stack.append(sign)
                res, sign = 0, 1
            elif c == ')':
                res += num * sign 
                num, sign = 0, 1 
                res *= stack.pop() #stack.pop() is the sign before the parenthesis
                res += stack.pop() #stack.pop() now is the result calculated before the parenthesis
        
        if num != 0:
            res += num * sign 
        
        return res 

88 https://leetcode.com/problems/merge-sorted-array/

끝에서부터 다시 채워준다.

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        while n > 0:
            if m > 0 and nums1[m-1] > nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1

981 https://leetcode.com/problems/time-based-key-value-store/

은근히 구현하는데 시간이 걸렸다. 처음에는 이진 탐색 트리를 구현해서 set을 할때도 탐색을 했었는데 그렇게 구현하니 시간초과가 났다. 고민하다 set에는 데이터를 그냥 넣고 get에서만 이분 탐색을 구현하니 통과했다. 

class TimeMap(object):
    def __init__(self):
        self.mydict = {}

    def set(self, key, value, timestamp):
        if key not in self.mydict:
            self.mydict[key] = [[value, timestamp]]
        else:
            self.mydict[key].append([value, timestamp])

    def get(self, key, timestamp):
        if key not in self.mydict:
            return ''
        else:
            v_list = self.mydict[key]
            l, r = 0, len(v_list)-1
            while l < r:
                m = (l + r + 1) / 2
                if v_list[m][1] <= timestamp:
                    l = m
                else:
                    r = m-1
            if v_list[l][1] <= timestamp:
                return v_list[l][0]
            return ''

연습을 위해 이분 탐색을 구현했지만 실전에서는 bisect모듈을 써서 풀것 같다.

127 https://leetcode.com/problems/word-ladder/

처음에 그냥 짰는데 통과는 했는데 너무 느렸다.

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        ret = []
        word_order_dict = {}
        for word in wordList + [beginWord]:
            word_order_dict[word] = set([(b, i) for i, b in enumerate(word)])

        visited = {beginWord: 1}
        queue = deque([[beginWord, 1]])
        while queue:
            p = queue.popleft()
            if p[0] == endWord:
                ret.append(p[1])
                continue

            for word in wordList:
                if word not in visited and len(word_order_dict[p[0]] & word_order_dict[word]) == len(beginWord) - 1:
                    visited[word] = p[1] + 1
                    if ret and p[1] + 1 >= min(ret):
                        continue
                    queue.append([word, p[1] + 1])

        return min(ret) if ret else 0 

다른 사람의 코드를 살펴보니 내 코드에서 매번 wordList를 전체 순회하는게 너무 오래걸리는것 같다. 미리 현재 word에서 갈수 있는 다른 word들을 전처리해두고 가도록 처리해야 정상적인 범위 내로 통과가 된다.

from collections import deque

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        word_dict = {}
        for word in wordList:
            for i in xrange(len(beginWord)):
                key = word[:i]+'*'+word[i+1:]
                word_dict[key] = word_dict.get(key, []) + [word]
                
        queue = deque([(beginWord,1)])
        visited = set(beginWord)
        ret = []
        while queue:
            p = queue.popleft()
            for i in xrange(len(beginWord)):
                _next = p[0][:i] +'*' + p[0][i+1:]
                for word in word_dict.get(_next, []):
                    if word == endWord:
                        ret.append(p[1] + 1)
                        continue
                    if word not in visited:
                        visited.add(word)
                        queue.append((word, p[1]+1))
                        
                word_dict[_next] = []
        return min(ret) if ret else 0