leetcode 787(다익스트라), 241(dp, 분할정복)

787 https://leetcode.com/problems/cheapest-flights-within-k-stops/

아주 오랫만에 보는 다익스트라 문제다. 기존에 풀던 다익스트라와 차이를 적자면, K번 stop이라는 횟수제한이 있어서 이 제한조건을 충족시켜야 한다.

from collections import deque

class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, K):
        adj = [[] for i in xrange(n)]
        for s,e,w in flights:
            adj[s].append([e, w])
        
        dist = [float('inf') for i in xrange(n+1)]
        dist[src] = 0
        q = deque()
        q.append([src, 0, 0])
        while q:
            here, cost, k_count = q.popleft()
            if k_count > K:
                continue
            for i in xrange(len(adj[here])):
                there = adj[here][i][0]
                nextdist = cost + adj[here][i][1]
                if dist[there] > nextdist:
                    dist[there] = nextdist
                    q.append([there, nextdist, k_count + 1])
        return dist[dst] if dist[dst] != float('inf') else -1

241 https://leetcode.com/problems/different-ways-to-add-parentheses/

dp, 분할정복 문제다. -+*부호가 나오면 부호를 기점으로 앞과 뒤로 나누어서 다시 잘개 쪼개기를 반복한다. 쪼개다가 숫자밖에 안남으면 숫자를 리턴시켜주고, 이미 했던 수식이면 메모이제이션해준다. 

수식의 모든 경우에 대해서 모든 나올수 있는 경우를 가지고 와야 하므로 모든 경우의 수에 대해 돌려준다.

class Solution(object):
    def diffWaysToCompute(self, input):
        visited = {}
        def helper(input):
            if input in visited:
                return visited[input]
            elif input.isdigit():
                return [int(input)]

            ret = []
            operator = {'+': lambda x,y: x+y,
                        '-': lambda x,y: x-y,
                        '*': lambda x,y: x*y}
            for i, c in enumerate(input):  # 하나하나 돌면서
                if c in "+-*":  # 수식이 나오면 좌, 우로 쪼갠후 재귀하면서 분할정복으로 계속 쪼갠다. 결국 숫자가 나올때까지.
                    for right in helper(input[i+1:]):
                        for left in helper(input[:i]):
                            ret.append(operator[c](left, right))  # 나온 숫자로 만들어진 값을 추가해놨다가 리턴한다.
            visited[input] = ret
            return ret
        
        return helper(input)