[알고리즘]9번째 알고리즘 풀이

[seroak]

📝 Description

무엇을?

• 9번째 알고리즘 풀이

❗️Todo

• [x] 첫번째 문제
• [x] 두번째 문제

[seroak]

gas station https://leetcode.com/problems/gas-station/

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 전체를 더하는 변수가 필요함
        # 누적합을 구하면서 최저일때와 그떄의 인덱스를 구하는 변수가 필요함
        acc_total_sum = 0  # 누접합을 구하는 변수
        mn_idx = 0  # 최소일때 인덱스 변수
        mn = 2**63 - 1  # 최소를 더하는 변수
        for i in range(len(gas)):
            sum_num = gas[i] - cost[i]
            acc_total_sum += sum_num
            if acc_total_sum <= mn:
                mn = acc_total_sum
                mn_idx = i
        if acc_total_sum >= 0:
            mn_idx += 1
            if mn_idx >= len(gas):
                mn_idx = 0
            return mn_idx
        else:
            return -1

[seroak]

Jump Game II

import sys
from collections import deque
class Solution:

    def jump(self, nums: List[int]) -> int:
        dist = [sys.maxsize] * len(nums)

        queue = deque()
        dist[0] = 0
        # queue(현재 인덱스, 점프할 수 있는 거리, depth)
        queue.append((0, nums[0], 1))
        while queue:
            cur_idx, jump_dist, depth = queue.popleft()
            for i in range(cur_idx+1, cur_idx + jump_dist+1):
                # 점프한 거리가 전체 인덱스를 넘어서면 빠져나온다
                if i >= len(nums):

                    break
                # 한번 방문한 곳은 빠져나온다
                if dist[i] != sys.maxsize:

                    continue
                dist[i] = min(dist[i], depth)
                queue.append((i, nums[i], depth + 1))
        return dist[-1]