[leetcode] (Swift) 134 - Gas station (Medium, 그리디)

 

 

역시 리트코드는,, 영어라서 문제 읽고 이해하는데 좀 더 걸린다. 하하하하하하하하하하
읽고 몇번은 더 정확하게 내가 해석한게 맞는지 확인하는 과정이 필요하다.... 

🟠 문제

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

Gas Station - LeetCode

영어인만큼 문제를 조금 설명해보자.

문제에서는 [Int] 형의 gas 배열과 cost배열 두개가 주어진다. 두개의 길이는 같고, 최대 10^5길이까지 늘어날 수 있다.

< 배열이 의미하는 것>
gas[i] 는 i번째 주요소에서 얻을 수 있는 gas의 양을 의미한다.
cost[i] 는 cost[i]에서 cost[i+1]까지 가는 데 드는 비용 (소모되는 가스의 양)을 의미한다. 

그럼 3번 주유소에서 4번주유소로 가게 되면, 3번주유소에 있는 gas[3]만큼 채우고, cost[3]만큼 소비하고, 4에 도착해서 gas[4]를 채우겠지?

<문제>
우리는 결국 시작점으로 돌아와야하는 문제다. 3번주유소에서 여행을 시작했다면, 다시 3번으로 돌아와야한다. 3,4,5,1,2, 이렇게! 우리는 이 시작점을 찾아야한다.
가스가 부족하면 움직일수없겠지? 그래서 적절한 시작점을 찾아서 리턴해주고, 만약 시작점을 찾을 수 없는 배열이 주어진다면 -1을 리턴해주어야한다. 

 

🟠 첫번째 - 광기의 테케 통과 실패 - 시간초과!

아니 테케 진짜 욕나오네.. 광기아니냐이거! 어쨌든 시간초과를 해결해야한다..(길이가 xcode에 붙여넣으면 멈추는 정도로 길다.. 10^5 길이로 넣은듯 ;)

❌ 틀린 코드

class Solution {
    func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
        for startNum in 0..<gas.count {
            var answer = 0
            var isPossibleTravel = true
            // 내부를 차례대로 순환하면서 더해주기
            for idx in startNum..<gas.count+startNum {
                let index = idx % gas.count
                answer += gas[index] - cost[index]

                if answer < 0 {
                    isPossibleTravel = false
                    break
                }
            }

            if isPossibleTravel {
                return startNum
            }
        }

        return -1
    }
}

이중 포문을 사용했다. 중간에 만족하지 않는 경우 break를 걸어주는 장치가 있지만 ,, 10^5가 들어오고, 저렇게 0이 무한대로 늘어선 경우에 어쩔 수없이 몇억번의 반복문이 돌아가게 되겠지.. 시간복잡도는 O(n^2)으로 보인다. 이것을 O(n)으로 해결할 순 없을까?

✅ break 조건을 사전에 걸어주고, 미리 계산을 떄려버리자

문제를 보면서 느낀게, 결국 gas[idx] - cost[idx] 들의 합이 마이너스가 나오면 안되는 문제였다. 이 부분을 첫번째 시도에서는 전부 for문 내부에서 계산해주면서 여러번 계산을 수해하게 했다. 10만개가 들어오면, 10만번의 for문을 돌면서 계속적으로 연산을 하게 되어있엇지... 그래서 이부분을 미리 계산하고, break문을 걸어주면 어떨지 생각했다.

// 일단 차액 다 계산해
let gasCostArr = (0..<gas.count).map{ gas[$0] - cost[$0] }

// 먼저 안되면 나가버려
if gasCostArr.reduce(0,+) < 0 {
    return -1
}

이렇게 map을 이용해서 미리 차액을 전부 게산해서 새로운 array에 넣어주었고, reduce 고차함수를 사용해서 또한 합을 구해보고, 합이 만약 음수가 되면 -1이 되도록 리턴했다. 

✅ 그리고 O(n)이 되려면 for문을 한번만 사용할 순 없을까?

우선 포문을 줄여야했다. 범위가 10^5까지 주어졌기 때문에 이중for문을 돌리게 되면,, 최대 10억번의 for loop이 돌아간다. 말도안된다... 1초에 1억이니까,, 10초!?!? 어우 말도안돼

생각이 필요했다... 

1. 먼저 전체의 합이 무조건 0 이상인걸 확인했다.
2. 스타트지점부터 차근차근 더해나갔을때 마지막 번호까지 도달한 경우, 그 합이 0보다 크면, 조건에 부합한거다! 왜냐면, 앞에있는 모든 수를 모조리 더하는 조건도 만족하는거고, 앞에서 부터 더했을때 음수가 나오는 경우는 사전에 차단해주었기 때문

그러면,, 앞에서 부터 차근차근 합을 확인하고, 음수가 나오면 그자리부터 다시 합을 새로구하고, 그 자리의 인덱스로 answer를 갱신해주면 되겠구나..?

 

🟠 정답코드

for문 한번쓰는게 로직생각하는게 생각보다 쉽지 않네..? 흠..

class Solution {
    func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
        let gasCostArr = (0..<gas.count).map{ gas[$0] - cost[$0] }

        if gasCostArr.reduce(0,+) < 0 {
            return -1
        }

        var answerIdx = 0
        var sum = 0

        for startNum in 0..<gas.count {
            sum += gasCostArr[startNum]
            if sum < 0 {
    	        // 여기서 보면 sum이 마이너스되는순간 그냥 0으로 갱신해서 새롭게 시작해버리고
	            // answerIdx를 지금인덱스바로 뒤에있는 인덱스로 옮겨버리기
                sum = 0
                answerIdx = startNum + 1
            }
        }
        return answerIdx > gas.count ? -1 : answerIdx
    }
}

 

우와 리트코드 짱좋다.

이렇게 내가 푼 코드에 대한 runtime과 메모리 효율이 어느정도인지 알려준다. 시간복잡도는 보통 사람들보다 조금 ,,, 뒤쳐지지만 메모리 효율로 봤을 때는 나쁘지 않았다.

그럼 진짜 초고수님들은 어떻게 짜는지 궁금해서 살펴봤다.

음,, 코드에서 다른 점은 cost와 gas의 합을 따로따로 구하고 그 둘을 비교해주었다.
나는 이 과정에서, gas와 cost의 차를 따로 계산 , 그리고 그 합을 계산했다. 아무래도 gas와 cost의 인덱스를 비교하고, 그 인덱스들의 차이를 다시 배열로 리턴하는 map을 사용하는 과정에서 조금더 시간이 들지 않았을까?

역시나 이 코드가 map을 사용해서 따로 배열을 return 한게 아니었기 때문에 메모리적인 측면에서도 나의 코드보다 더 좋았다. 오호,,, 풀이과정은 똑같다고 봐도 무방한데, 어떻게 어떤 고차함수를 사용하고 어떤 자료구조를 사용해서 코드를 짜느냐에 따라서 이렇게나 효율이 달라지는군.. 새삼 한번.. 더... 몸소 .. 느끼고 떠납니다... 🫠 멋지다...고수들