leetcode 1823(조세퍼스 문제, 구현), 1448(트리, 재귀), 1396(구현)

1823 https://leetcode.com/problems/find-the-winner-of-the-circular-game/
딱봐도 문제가 원형 이중연결리스트처럼 생겨서 이걸 만들어서 풀었다. 근데 시간이 많이 느리다.. 뭐지 하고 다른 답을 봤는데 아주 예전에 풀었던 조세퍼스(요세푸스) 문제였다. https://qkqhxla1.tistory.com/707
본지 하두 오래돼서 잊어먹고 있었다. 

원형 이중연결리스트.

class Node:
    def __init__(self, v):
        self.val = v
        self.next = None
        self.prev = None
        
class Solution(object):
    def findTheWinner(self, n, k):
        start_node = cur_node = Node(1)
        prev_node = None
        for i in xrange(2, n + 1):
            new_node = Node(i)
            cur_node.next = new_node
            cur_node.prev = prev_node
            prev_node = cur_node
            cur_node = new_node
        cur_node.next = start_node
        cur_node.prev = prev_node
        start_node.prev = cur_node
        
        index = 1
        cur_node = start_node
        while cur_node.next.val != cur_node.val:
            if index % k == 0:
                cur_node.prev.next = cur_node.next
                cur_node.next.prev = cur_node.prev
            cur_node = cur_node.next
            index += 1
        return cur_node.val  

조세퍼스.

class Solution(object):
    def findTheWinner(self, n, k):
        friends = range(1, n+1)
        while len(friends) != 1:
            for i in xrange(k-1):
                friends.append(friends.pop(0))
            friends.pop(0)
        return friends[0]

deque를 적극적으로 쓰면 속도가 10배 이상 빨라진다. https://leetcode.com/problems/find-the-winner-of-the-circular-game/discuss/1219319/Python-Simple-Deque-36-ms-easy-solution

1448 https://leetcode.com/problems/count-good-nodes-in-binary-tree/ 재귀로 짠다.

class Solution(object):
    good_node_count = 0
    def goodNodes(self, root, max_val=float('-inf')):
        if not root:
            return
        if max_val <= root.val:
            self.good_node_count += 1
        self.goodNodes(root.left, max(root.val, max_val))
        self.goodNodes(root.right, max(root.val, max_val))
        return self.good_node_count

1396 https://leetcode.com/problems/design-underground-system/ 설명을 읽기보다 예제코드를 보고 이해하자..
설명보다는 예제를 보는게 이해하기가 더 쉽다. 중 난이도인데 쉬움 난이도로 봐도 될것같다.

class UndergroundSystem(object):
    def __init__(self):
        self.check_in_out_dict = {}
        self.time_dict = {}

    def checkIn(self, id, start_station, t):
        self.check_in_out_dict[id] = [start_station, t]

    def checkOut(self, id, end_station, end_time):
        start_station, start_time = self.check_in_out_dict[id]
        key = start_station + '->' + end_station
        self.time_dict[key] = self.time_dict.get(key, []) + [end_time - start_time]

    def getAverageTime(self, start_station, end_station):
        value = self.time_dict[start_station + '->' + end_station]
        return sum(value)/float(len(value))