[Python : 프로그래머스] 다리를 지나는 트럭

문제

https://programmers.co.kr/learn/courses/30/lessons/42583

풀이

문제를 처음 읽었을 당시 실제로 큐에 값이
차례로 Insert / POP 되는 형태보다
weight를 넘지 않는 인접값끼리 한 꺼번에
처리하면 좋지 않을까 하며 그림을 그려봤다.

truck_weights : [7, 4, 5, 1, 6]
bridge_length : 3
weight : 10
--------------------------------
7 | 4, 5, 1 | 6
(3+0) + (3+2) + (3+0) = 11

한 번에 건널 수 있는 트럭의 개수를 나누고
길이 + (트럭수-1)로 값을 뽑아내서 더해보니
그럴듯 한 답이 나왔다.
그래서 바로 시도해봤던 코드

def solution(bridge_length, weight, truck_weights):
    Q = []
    for tw in truck_weights :
        if len(Q)==0 or Q[-1][0]+tw > weight :
            Q.append([tw, 1])
        else :
            Q[-1][0] += tw
            Q[-1][1] += 1
    
    return sum((q[1]-1)+bridge_length for q in Q)

이전 포스팅에서 배웠던 빈 Q를 알아내는 방법이나,
Q를 해시처럼 이용한 것은 좋았으나, 정답이 아니었다.
어떡하나 고민해보다가, 쉽게 시도했을 때 해결되는 사례도 있었기 때문에
이번에도 쉬운 방법으로 시도해봤다.

def solution(bridge_length, weight, truck_weights):
    bridge = [0 for i in range(bridge_length)]
    sec = 0

    while bridge:
        sec += 1
        bridge.pop(0)

        if truck_weights:
            if sum(bridge)+truck_weights[0] <= weight:
                bridge.append(truck_weights.pop(0))
            else:
                bridge.append(0)

    return sec

성공이네?
그런데 역시 걱정한대로 속도가 어마무시하다…

테스트 1 〉	통과 (13.05ms, 10.2MB)
테스트 2 〉	통과 (1501.33ms, 10.3MB)
테스트 3 〉	통과 (0.03ms, 10.3MB)
테스트 4 〉	통과 (335.04ms, 10.4MB)
테스트 5 〉	통과 (9623.82ms, 10.2MB)
테스트 6 〉	통과 (1569.48ms, 10.2MB)
.
.
.

특히 테스트 5번의 경우 9.6초…
프로그래머스 채점 제한시간인 10초에 걸릴 뻔 했다.

pop(0) 함수가 맨 좌측의 요소를 제거하고
뒤 값들을 한 칸씩 당겨오기 떄문에
시간을 잡아먹는 주범이라길레
Deque도 사용해보고 Queue를 reverse도 시켜봤으나
별다른 차이를 보여주지 못했다.

아무리 생각해도 좋은 풀이는 아니었다.
더 나은 풀이를 찾아봐야겠다.

더 나은 풀이

import collections

DUMMY_TRUCK = 0


class Bridge(object):

    def __init__(self, length, weight):
        self._max_length = length
        self._max_weight = weight
        self._queue = collections.deque()
        self._current_weight = 0

    def push(self, truck):
        next_weight = self._current_weight + truck
        if next_weight <= self._max_weight and len(self._queue) < self._max_length:
            self._queue.append(truck)
            self._current_weight = next_weight
            return True
        else:
            return False

    def pop(self):
        item = self._queue.popleft()
        self._current_weight -= item
        return item

    def __len__(self):
        return len(self._queue)

    def __repr__(self):
        return 'Bridge({}/{} : [{}])'.format(self._current_weight, self._max_weight, list(self._queue))


def solution(bridge_length, weight, truck_weights):
    bridge = Bridge(bridge_length, weight)
    trucks = collections.deque(w for w in truck_weights)

    for _ in range(bridge_length):
        bridge.push(DUMMY_TRUCK)

    count = 0
    while trucks:
        bridge.pop()

        if bridge.push(trucks[0]):
            trucks.popleft()
        else:
            bridge.push(DUMMY_TRUCK)

        count += 1

    while bridge:
        bridge.pop()
        count += 1

    return count


def main():
    print(solution(2, 10, [7, 4, 5, 6]), 8)
    print(solution(100, 100, [10]), 101)
    print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]), 110)


if __name__ == '__main__':
    main()

Bridge 클래스를 직접 작성해서 풀어낸 코드
‘이렇게 짤거면 C++ 이나 Java가 낫지 않나?’
라는 생각이 많이 들어서, 개인적으로는 잘 모르겠다.

아마 Deque을 이용하고, if문 조건을 최대한 깔끔하게 설정해서
Deque에 변화가 일어나는 것을 최소한으로 막았기 때문에
속도는 빠른지 않을까 예상해본다.