[Python] Leetcode 134. Gas station

목차

문제

---

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

Gas Station - LeetCode

 

설계&풀이

---

정말 간만에 머리를 앓았던 문제라서 포스팅한다.

코테에서 자주 보이던 그리디 문제인데, 처음엔 완탐으로 했다가 시간초과가 났다.

	# 시간초과 풀이...
    # 한바퀴 만큼 순회
    n = len(gas)
    
    if n == 1:
        if gas[0] >= cost[0]:
            return 0
        else:
            -1
    
    for i in range(n):
        if gas[i] > cost[i]:
            remainGas = gas[i]
            for j in range(i, n+i):
                # 끝 인덱스에서 처음인덱스로 가서 계산해야함
                # 4 ~ 9 면 인덱스는 4~8까지 실행
                # ex) i = 4, j = 4, index = 0 ...
                # ex) i = 4, j = 5, index = 1 ...
                # ex) i = 4, j = 8, index = 4 ...
                
                # j가 n보다 클때
                if j >= n:
                    remainGas -= cost[j-n]
                    if remainGas >= 0:
                        remainGas += gas[j-n+1]
                
                # j가 마지막 인덱스에서 처음 인덱스로 갈 때
                elif j == n-1:
                    remainGas -= cost[j]
                    if remainGas >= 0:
                        remainGas += gas[0]
                
                # 처음과 끝 사이에서 움직일 때
                else:
                    remainGas -= cost[j]
                    if remainGas >= 0:
                        remainGas += gas[j+1]
            if remainGas > 0:
                return i
    return -1

 n 이 주어진 gas의 길이라고 할 때,

2중 for문을 돌면서 이 인덱스가 1바퀴 순회가 가능한지 판단한다.
이 때, 마지막 인덱스일 때, 마지막 인덱스의 크기보다 클 때, 0~n 사이일 때 3가지 케이스로 분류해서 계산한다.

결과는 시간초과... 어찌보면 당연했다. 결국 답지를 찾아봤는데..

# 1바퀴 돌만큼의 기름이 없는경우엔 -1 리턴
    if sum(gas) < sum(cost):
        return -1

    start, fuel = 0, 0
    for i in range(len(gas)):
        # 출발점이 안 되는 지점 판별
        if gas[i] + fuel < cost[i]:
            start = i + 1
            fuel = 0
        else:
            fuel += gas[i] - cost[i]
    return start

 세상 간단한 코드...
그런데 여기서도 gas[i] + fuel < cost[i] 이부분 만으로 어떻게 출발점을 판단한다는거지?
1번 예제를 예로 든다면..

"4번째 인덱스에서 0번째 인덱스로 갈 때, 기름이 모자랄 수도 있잖아? 이건어떻게 체크할거지?"

라는 생각에 사로잡혀서 이해가 오래걸렸던 것 같다. 직접 디버깅을 해본 결과, 이런 케이스는 위에 sum에서 걸러진다;;
그래서 현재 gas에서 충전할 수 있는 가스량과, 보유중인 fuel의 합이 cost보다 많기만 하면 순회가 가능하다는 것은 보장이 되는것... 그리고 또 하나 중요한 요소는 정답은 하나뿐이다. 라는것이다.

그렇기에, 현재 출발점을 찾고 나면 나머지는 굳이 안봐도 되는것이었다.

그리디... 참 ㅠㅠ 단순하게 생각해야지만 어찌보면 복잡하기도 한것..

코드 GIT 주소

---

https://github.com/kkkapuq/AlgorithmStudy/blob/main/Python/221003_Leetcode_134.%20Gas%20Station/1.py

GitHub - kkkapuq/AlgorithmStudy: 알고리즘 문제풀이

 

코드

---

from collections import deque

def canCompleteCircuit(gas: list[int], cost: list[int]):
    
    '''
    시간초과 풀이...
    # 한바퀴 만큼 순회
    n = len(gas)
    
    if n == 1:
        if gas[0] >= cost[0]:
            return 0
        else:
            -1
    
    for i in range(n):
        if gas[i] > cost[i]:
            remainGas = gas[i]
            for j in range(i, n+i):
                # 끝 인덱스에서 처음인덱스로 가서 계산해야함
                # 4 ~ 9 면 인덱스는 4~8까지 실행
                # ex) i = 4, j = 4, index = 0 ...
                # ex) i = 4, j = 5, index = 1 ...
                # ex) i = 4, j = 8, index = 4 ...
                
                # j가 n보다 클때
                if j >= n:
                    remainGas -= cost[j-n]
                    if remainGas >= 0:
                        remainGas += gas[j-n+1]
                
                # j가 마지막 인덱스에서 처음 인덱스로 갈 때
                elif j == n-1:
                    remainGas -= cost[j]
                    if remainGas >= 0:
                        remainGas += gas[0]
                
                # 처음과 끝 사이에서 움직일 때
                else:
                    remainGas -= cost[j]
                    if remainGas >= 0:
                        remainGas += gas[j+1]
            if remainGas > 0:
                return i
    return -1 
    '''
    
    # 1바퀴 돌만큼의 기름이 없는경우엔 -1 리턴
    if sum(gas) < sum(cost):
        return -1

    start, fuel = 0, 0
    for i in range(len(gas)):
        # 출발점이 안 되는 지점 판별
        if gas[i] + fuel < cost[i]:
            start = i + 1
            fuel = 0
        else:
            fuel += gas[i] - cost[i]
    return start
    


canCompleteCircuit([1,2,3,4,5], [3,4,5,1,9])

 

결과

---

 

 

구독 및 하트는 정보 포스팅 제작에 큰 힘이됩니다♡