leetcode 1845(heap), 1557(graph, dfs), 1325(트리)

1845 https://leetcode.com/problems/seat-reservation-manager/
예약, 예약취소기능을 구현해야하고, 예약시에는 현재 예약가능한 좌석중에서 가장 번호가 낮은 좌석을 예약한다.
== 현재 리스트에서 항상 가장 번호가 낮은 좌석을 가져오려면 힙을 만들어서 pop만 해주면 된다.
예약취소시에 새로 들어온 숫자까지 합쳐서 매번 정렬하는것보다는 힙으로 구현하는게 더 시간복잡도가 적게걸린다.

import heapq
class SeatManager(object):
    def __init__(self, n):
        self.available_seat = range(1, n+1)
        heapq.heapify(self.available_seat)

    def reserve(self):
        return heapq.heappop(self.available_seat)

    def unreserve(self, seatNumber):
        heapq.heappush(self.available_seat, seatNumber)

1557 https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/
모든 노드에 도달하기 위해 최소한의 노드 리스트를 리턴하는 문제이다. dfs로 풀었는데...

from collections import deque
class Solution(object):
    def findSmallestSetOfVertices(self, n, edges):
        #n = 3
        #edges = [[1,2],[1,0],[0,2]]
        
        graph = {}
        for f,t in edges:
            graph[f] = graph.get(f, []) + [t]  # 갈수 있는 곳들을 저장해둔다.
        
        ret = set()
        visited = set()
        for node in xrange(n):  # 하나하나 돌면서
            if node in visited:  # 이전에 방문 안한 곳들만 방문
                continue
            ret.add(node)
            queue = deque([node])
            visited.add(node)
            while queue:
                n = queue.popleft()
                for _next in graph.get(n, []):  # 다음 방문 리스트
                    if _next in visited:  # 다음 방문할곳이 이미 방문했었으면 continue인데
                        if _next in ret:  # 다음 방문할곳이 결과 set에 있으면 지운다. 현 노드에서 도달 가능하기 때문이다.
                            ret.remove(_next)
                        continue
                    visited.add(_next)
                    queue.append(_next)
        return list(ret)

알고리즘 마스터의 접근방법 : https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/discuss/805685/JavaC%2B%2BPython-Nodes-with-no-In-Degree
1. 다른 노드로부터 도달 가능한 리스트에 없으면 일단 필요한 노드임.(혼자 따로 떨어져 있다는 소리이므로.) 
2. 다른 노드들은 또다른 노드들로부터 도달 가능함.

그러니까 아래 코드처럼 모든 노드(range(n))중에서 도달 가능 목록(set(j for i, j in edges))에 있는 애들을 제외하면 필수 노드들이라는 뜻

def findSmallestSetOfVertices(self, n, edges):
    return list(set(range(n)) - set(j for i, j in edges))

생각하는거 자체가 다르다.

1325 https://leetcode.com/problems/delete-leaves-with-a-given-value/
트리의 리프에 target이 있으면 리프를 없애버려야 한다. 리프를 없앤 후에 남아있는 리프중에 또 target이 있으면 리프를 지워야 한다. dfs로 푸는데, 재귀적인 dfs로 풀어야 한다. iterative하게 풀려면 모든 부모의 상태를 저장하는데에 이슈가 생긴다.

class Solution(object):
    def removeLeafNodes(self, root, target):
        def dfs(node):
            if not node:
                return
            node.left, node.right = dfs(node.left), dfs(node.right)  # 리프에서의 상태값을 업데이트받아서 사용함.
            if not node.left and not node.right and node.val == target:  # 리프노드가 target이면 없애버림.
                return
            return node
        return dfs(root)