릿코드 134. Gas Station, 135. Candy

문제

134. https://leetcode.com/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150

LeetCode - The World's Leading Online Programming Learning Platform

135. https://leetcode.com/problems/candy/description/?envType=study-plan-v2&envId=top-interview-150

LeetCode - The World's Leading Online Programming Learning Platform

134. 접근

n^2 밖에 안 떠올랐다.

    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1

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

for문은 한 번만 돌리고

sum_gas += gas[i] - cost[i]

sum_gas가 음수가 되면 start_idx를 갱신한다.

최소 인덱스라던가 제일 효율 좋은 여행이라던가 그런 조건이 없고 "If there exists a solution, it is guaranteed to be unique" 경우의 수는 하나라고 보장한다.

그런 접근으로 봤을 때, gas[i] - cost[i] 값이 i에서 양수, i+1에서 양수라면 start_idx를 i인 경우와 i+1인 경우를 따로 볼 이유가 없다. i와 i+1이 양수라면 i에서 시작하는 게 여행을 성공할 가능성이 더 높다.

135. 접근

i하고 i+1을 비교하면서 가는데

ratings[i] < ratings[i+1] 이 경우, 즉 left가 큰 경우 candy 수를 왼쪽으로 쭉 업데이트해야 한다. 이러면 n^2, 그래도 length가 10^4이라 혹시 몰라 돌려봤지만 Time Limit Exceeded이다.

    # Time Limit Exceeded
    def candy(self, ratings: List[int]) -> int:
        result = [ 1 for _ in range(len(ratings)) ]
        for i in range(len(ratings)-1):
            left, right = ratings[i], ratings[i+1]
            if left < right:
                result[i+1] = result[i] + 1
            elif right < left:
                if result[i] > result[i+1]:
                    continue
                result[i] = result[i+1] + 1
                j = i-1
                while j>-1:
                    if ratings[j] <= ratings[j+1]:
                        break
                    if result[j] <= result[j+1]:
                        result[j] = result[j+1] + 1
                    j -= 1     
        # print(result)
        return sum(result)

for문 한 번에 가져가려면 어떻게 할까 생각했다.

left > right 경우를 stack으로 쌓아두고

left <= right 경우 쌓은 stack을 flush 하는 느낌으로 접근했다.

stack은 result의 일부에 해당하는 리스트를 만들고

flush는 만든 list를 result에 slice 하여 대체한다.

    # 개선1
    def candy(self, ratings: List[int]) -> int:
        result = [ 1 for _ in range(len(ratings)) ]
        left_stack = [1]
        for i in range(len(ratings)-1):
            left, right = ratings[i], ratings[i+1]
            if left > right:
                left_stack.append(left_stack[-1] + 1)
            else:
                # left_stack flush
                if len(left_stack) > 1:
                    if left_stack[-1] < result[i-len(left_stack)+1]:
                        left_stack[-1] = result[i-len(left_stack)+1]
                    result[i-len(left_stack)+1:i+1] = left_stack[::-1]
                    left_stack = [1]
                
                if left < right:
                    result[i+1] = result[i] + 1
        
        # print(result, left_stack)
        # left_stack finish flush
        if len(left_stack) > 1:
            leng = len(result)
            if left_stack[-1] < result[leng - len(left_stack)]:
                left_stack[-1] = result[leng - len(left_stack)]
            result[leng-len(left_stack):leng] = left_stack[::-1]
        # print(result)
        return sum(result)

위에 로직에 left == right의 경우도 flush 한다. left_stack[-1]과 동일한 값을 append 하는 것도 문제가 있다.

동일한 값을 append 하면 ratings [3,2,2,1] 은 candy [3,2,2,1] 이 된다. candy [2,1,2,1]가 나와야 하므로 flush

 

마지막이 left > right로 끝나면 flush를 안 하므로 반복문 밖에서 챙겨준다.

 

통과하고 시간도 괜찮은데 flush 하면서 slice 위치 잡는 것과 경우의 수를 놓칠 가능성이 높다.

다른 답을 살펴봤다.

    # 개선2
    def candy(self, ratings: List[int]) -> int:
        candy=[1]*len(ratings)
        for i in range(1,len(ratings)):
            if ratings[i-1]<ratings[i]:
                candy[i]=candy[i-1]+1
        for i in range(len(ratings)-2,-1,-1):
            if ratings[i+1]<ratings[i] and candy[i+1]>=candy[i]:
                candy[i]=candy[i+1]+1
        return sum(candy)

오른쪽으로 먼저 돌리면서 상승하는 result를 잡고

왼쪽으로 돌리면서 떨어지는 result를 잡는다.

 

개선 2는 2n이고 개선 1은 n인데 slice가 있어서 개선 2보다 약간 느렸다.

시간보다는 코드가 샐 데가 없는 게 개선 2가 훨씬 낫다.