https://leetcode.com/problems/longest-substring-without-repeating-characters/

가장 긴 문자열을 찾는 문제 처음부터 끝까지 문자열을 스캔하면서 dictionary에 각 문자가 등장한 index를 저장하면서 가장 긴 문자열의 길이를 저장해나가는 방식 이미 등장한 문자가 또 등장했을 경우, 문자열의 시작 위치를 이전 문자열의 등장 idx와 현재 들고 있던(다른 문자들에 의한) idx와 비교하여 큰 쪽으로 설정

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        buf = {}
        answer = 0
        now = 0
        start = 0
        for idx, elem in enumerate(s):
            if elem in buf:
                start = max(buf[elem] + 1, start) # 다른 문자에 의한 start와 현재 문자의 start중 큰값
                now = idx - start +1
            else:
                now+=1
            answer = max(answer, now)

            buf[elem] = idx
        return answer

def solution(nodeinfo):
    # call stack이 100만을 넘어가는 경우가 문제에 존재하여 runtime error 발생 해결
    import sys
    sys.setrecursionlimit(10**6)

    #예외처리    
    if len(nodeinfo) == 1:
        return [[1], [1]]

    class BTree:
        def __init__(self, x, y, idx):
            self.x = x
            self.y = y
            self.idx = idx
            self.left = None
            self.right = None

    # 주어진 x, y좌표를 트리의 노드로 생성
    nodes = []
    for idx, (x, y) in enumerate(nodeinfo):
        node = BTree(x, y, idx+1)
        nodes.append(node)
    #노드들을 정렬하는데 트리의 높이, 트리의 x좌표를 기준으로 정렬
    nodes.sort(key = lambda elem: (elem.y, -elem.x))

    # 트리를 같은 level 에 속하는 node끼리 묶어줌
    node = nodes.pop()
    tree = [[node]]
    cache = node.y
    level = 0
    while nodes:
        node = nodes.pop()
        if not node.y == cache:
            level +=1
            cache = node.y
            tree.append([node])
        else:
            tree[level].append(node)

    # tree의 node들을 서로 연결. level 회수만큼 root에서 타고 내려가는데, x좌표를 기준으로 left rigt판별
    for level in range(1, len(tree)):
        for node in tree[level]:
            root = tree[0][0]
            for i in range(level-1):
                if node.x < root.x :
                    root = root.left
                else:
                    root = root.right
            if node.x < root.x:
                root.left = node
            else:
                root.right = node

    # 서치
    pre_answer = []
    post_answer = []
    def preorder(node):
        pre_answer.append(node.idx)
        if node.left:
            preorder(node.left)
        if node.right:
            preorder(node.right)
    def postorder(node):
        if node.left:
            postorder(node.left)
        if node.right:
            postorder(node.right)
        post_answer.append(node.idx)

    preorder(tree[0][0])
    postorder(tree[0][0])
    return [pre_answer, post_answer]

DP list에 각 nums 인덱스에 도달할 수 있는 최소 회수를 저장하도록 함

class Solution:
    def jump(self, nums: List[int]) -> int:
        INF = 1e9
        length = len(nums)

        dp = [INF for i in range(length)]
        dp[0] = 0

        for i in range(length-1):
            now = nums[i]
            for dx in range(now):
                dx+=1
                if i + dx < length:
                    dp[i+dx] = min(dp[i+dx], dp[i] +1)

        return dp[-1]

문제는 실행시간이 끔찍하게 느리다는 점.

문제점 1. if로 length 를 넘는지를 계속 체크한다 -> 그냥 maximum list 사이즈를 확인한 후 dp list를 선언하면 length면 되는걸 length*평균(nums) 만큼 if를 더 태워버린 꼴

문제점 2. 애초에 이런 방식으로는 O(length * 평균(nums))임. 다른 방법을 찾아보니 시간복잡도 O(length)만으로 되는 코드를 발견

class Solution:
    def jump(self, nums: List[int]) -> int:
        last_index = len(nums) - 1
        max_reachable=[start_pos+nums[start_pos] for start_pos in range(last_index)]
        jump_range = (0, 0)
        n_jumps = 0
        while jump_range[1] < last_index:
            n_jumps += 1
            jump_range = (jump_range[1], 
                            max(max_reachable[jump_range[0]:jump_range[1]+1]))
        return n_jumps

각 time step 마다 도달할 수 있는 최대거리를 dp list에 저장하는 방식