[1스4코2파] # 248. LeetCode 134. Gas Station

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (248일차)
[4코1파] 2023.01.13~ (241일차)
[1스4코1파] 2023.04.12~ (152일차)
[1스4코2파] 2023.05.03 ~ (130일차)

Today :

2023.09.08 [248일차]
134. Gas Station
https://leetcode.com/problems/gas-station/description/

134. Gas Station

문제 설명

순환하는 n개의 주유소를 나타내는 배열 gas가 주어질 때, gas의 i번째 인덱스의 원소는 주유량을 나타낸다.
i번째 인덱스에서 (i + 1)번째 인덱스로 이동할 때는 cost가 발생하는데, 발생하는 cost에 대한 배열도 주어진다.

임의의 gas 인덱스에서 0인 상태로 두 개의 정수 배열 gas와 cost는 시계 방향으로 한 번 탐색을 시작할 수 있으면 시작 하는 gas의 인덱스를 반환하고 그렇지 않으면 -1를 return 함

문제 풀이 방법

brute force로 gas와 cost를 돌면서, gas와 cost에 대한 차를 구하고, 이 차를 구한 배열에서 탐색하면서 시작가능한 index를 찾아내면 시간복잡도 O(n^2) 가 나오게 된다.

greedy를 이용해서 두 배열을 한번 탐색하면서, base로는 gas의 합이 cost보다 작다면 시계방향으로 순환이 어렵기 때문에 -1을 return 한다. gas의 합이 cost 보다 높을 시에 탐색을 시작하면서, gas와 cost에 대한 차를 total 변수에 두고 이 total이 negative 하다면 total을 다시 0으로 reset하고 다음 인덱스 값을 answer 변수에 할당한다. 한번 탐색이 끝났을 때 최종적으로 answer에 있는 인덱스의 값이 순환이 가능한 인덱스로 판단하고 이를 return 하면 시간복잡도 O(n)임

내 코드

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        
        total = 0
        ans = 0

        for i in range(len(gas)):
            total += (gas[i] - cost[i])
            
            if total < 0:
                total = 0
                ans = i + 1
        
        return ans          

증빙

여담

시차적응 다했다고 생각했는데 시차적응 땜에 졸린건지
neetcode하니까 졸린건지 문제 풀다가 잠;;