leetcode 399(bfs, evalute-division), 406(구현), 304(prefix sum, dp), 303(prefix sum)

399 https://leetcode.com/problems/evaluate-division/

처음에 이게 bfs dfs탐색으로 풀수있는문제인지 아예 감을 못잡았다. discussion중에

https://leetcode.com/problems/evaluate-division/discuss/88275/Python-fast-BFS-solution-with-detailed-explantion

가 가장 유용했다. 요약하면 a/b가 2.0이면 a에서 b로 가는데 가중치가 2.0이라고 그래프형태로 저장해놓을수 있다. 

b/a는 0.5로 거꾸로도 저장해놓고 이런식으로 갈수있는 모든 경우의 수를 저장해놓는다. 그후에 갈수있는 이웃들을 전부 탐색하면서 해당 이웃으로 갈수 있으면 현재 값에 이웃으로 갈수 있는 가중치를 곱해주면 그게 답이다...

문제가 원래 이렇게 푸는게 정석인지는 모르겠는데 천재인것같다..

from collections import deque

class Solution(object):
    def calcEquation(self, equations, values, queries):
        graph = {}
        for point, value in zip(equations, values):
            graph[point[0]] = graph.get(point[0], []) + [[point[1], value]]  # a에서 b로 가는데 가중치가 value.
            graph[point[1]] = graph.get(point[1], []) + [[point[0], 1/value]]  # b에서 a로 가는데 가중치는 1/value.
            
        ret = []
        while queries:
            s, e = queries.pop(0)  # s,e는 start, end를 뜻함.
            if s not in graph or e not in graph:  # 둘중 하나라도 graph에 없으면 도달할수 없다는 뜻이므로 -1
                ret.append(-1.0)
                continue
            elif s == e:  # 같으면 1.0
                ret.append(1.0)
                continue
                
            queue = deque([[s, 1.0]])
            visited = set([s])
            find = False
            while queue:
                node, cur_value = queue.popleft()
                if node == e:  # 이웃들을 들러들러 end에 도달했으면 성공인 경우
                    ret.append(cur_value)
                    find = True
                    break
                
                for neighbor, value in graph[node]:
                    if neighbor in visited:
                        continue
                    visited.add(neighbor)
                    queue.append([neighbor, cur_value * value])
            if not find:
                ret.append(-1.0)
        return ret

406 https://leetcode.com/problems/queue-reconstruction-by-height/

class Solution(object):
    def reconstructQueue(self, people):
        people = sorted(people, key = lambda x: (-x[0], x[1]))  # 키가 큰 순서대로, 그다음엔 앞에 몇명이 있는지 순으로 정렬해준다.
        res = []
        # 키가 큰 순서부터 돌아가며 새 리스트에 앞에 몇명이 있는지 인덱스에 따라 삽입한다. 
        # 키가 큰 순서대로 먼저 정렬하는 이유는 키가 작은 사람이 나중에 정렬함으로서 키가 작은 사람이 더 앞에 오도록 하기 위함이다
        for p in people:  
            res.insert(p[1], p)
        return res

304 https://leetcode.com/problems/range-sum-query-2d-immutable/

토픽은 dp이면서 2차원 prefix sum으로 보면 될것같다.

class NumMatrix(object):
    def __init__(self, matrix):
        if matrix is None or not matrix:
            return
        m, n = len(matrix), len(matrix[0])
        self.prefix_sum = [[0]*(n+1) for i in xrange(m+1)]
        for i in xrange(1, m+1):
            for j in xrange(1, n+1):
                # i,j까지의 합은 matrix[i-1][j-1] + i,j-1까지의 합 + i-1,j까지의 합 - i-1,j-1까지의 합.(i-1,j-1까지의 합을 한번 빼주는 이유는 두번 더해줘서이다.)
                self.prefix_sum[i][j] = matrix[i-1][j-1] + self.prefix_sum[i][j-1] + self.prefix_sum[i-1][j] - self.prefix_sum[i-1][j-1]
                
    def sumRegion(self, row1, col1, row2, col2):
        # 이것도 위와 동일하다. 오른쪽 아래의 합에서 중복되는 부분들을 빼준후 두번 빠진 부분을 한번 더해주면 된다.
        return self.prefix_sum[row2+1][col2+1] - self.prefix_sum[row2+1][col1] - self.prefix_sum[row1][col2+1] + self.prefix_sum[row1][col1]

303 https://leetcode.com/problems/range-sum-query-immutable/

prefix sum 가장 기초 문제

class NumArray(object):
    def __init__(self, nums):
        for i in xrange(1, len(nums)):
            nums[i] += nums[i-1]
        self.nums = nums
        
    def sumRange(self, i, j):
        return self.nums[j] if i == 0 else self.nums[j] - self.nums[i-1]