[leetcode] 3-9회차

https://leetcode.com/problems/evaluate-division/?envType=study-plan-v2&envId=top-interview-150

class Solution(object):
    def calcEquation(self, equations, values, queries):
        """
        :type equations: List[List[str]]
        :type values: List[float]
        :type queries: List[List[str]]
        :rtype: List[float]
        """
        G = collections.defaultdict(dict)

        for (x, y), v in zip(equations, values):
            G[x][y] = v
            G[y][x] = 1/v

        def bfs(src, dst):
            if not (src in G and dst in G): return -1.0
            q, seen = [(src, 1.0)], set()
            for x, v in q:
                if x == dst:
                    return v

                seen.add(x)
                for y in G[x]:
                    if y not in seen:
                        q.append((y, v*G[x][y]))
            return -1.0
        return [bfs(s,d) for s, d in queries]

문제가 20분동안 안풀려서 답안을 봤다. 처음에 유니온파인드로 풀면된다고는 생각했는데 유니온 파인드 문제도 bfs 로 풀리는 걸 알게 되었다. 

 

def calcEquation(equations, values):
	root = {}
	
	# xr = x/parent(x), pr = parent(x)/root(x), update xr to xr*pr = x/root(x)
	def find(x):
		p, xr = root.setdefault(x, (x, 1.0))
		if x != p:
			r, pr = find(p)
			root[x] = (r, xr*pr)
		return root[x]

	# if root(x) = root(y), equations "x / y" doable as (x/root(x)) / (y/root(y)) = xr / yr
	def union(x, y, ratio):
		px, xr, py, yr = *find(x), *find(y)
		if not ratio:
			return xr / yr if px == py else -1.0
		if px != py:
			root[px] = (py, yr/xr*ratio)

	for (x, y), v in zip(equations, values):
		union(x, y, v)
	return [union(x, y, 0) if x in root and y in root else -1.0 for x, y in queries]

유니온으로 풀어준 부분도 있었다. 

 

https://leetcode.com/problems/course-schedule/?envType=study-plan-v2&envId=top-interview-150

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        graph = [[] for _ in xrange(numCourses)]
        visit = [0 for _ in xrange(numCourses)]
        for x, y in prerequisites:
            graph[x].append(y)
        def dfs(i):
            if visit[i] == -1:
                return False
            if visit[i] == 1:
                return True
            visit[i] = -1
            for j in graph[i]:
                if not dfs(j):
                    return False
            visit[i] = 1
            return True
        for i in xrange(numCourses):
            if not dfs(i):
                return False
        return True

사이클 판단 문제라는 것까지 유추했는데 코드 작성이 어렵다.. 계속 코드를 쓰는 연습을 해야할 것 같다.