[Level 2] 스택/큐. 다리를 지나는 트럭

 문제 

https://programmers.co.kr/learn/courses/30/lessons/42583?language=python3 

코딩테스트 연습 - 다리를 지나는 트럭

 사용 언어 

Python3

 풀이 과정 

하아... 변수 설정부터 뭐뭐가 필요한지 고민하고 처음으로 메모장에 의사코드를 먼저 작성해봤다.

작성하다 보니 의사코드와 살짝씩 달라졌지만 갈수록 어려운 문제를 풀 것이니 처음 방향 설정에 도움이 되는 것 같다.

그리고 처음으로 브레이크 포인트를 추가해 디버깅을 해서 변수값이 달라지는 것을 보며 오류를 찾은 점이 뿌듯하다.

 

중간에 인덱스 에러와 잘못된 결괏값의 출력으로 고생을 좀 했지만 약 3시간만에 푼 문제!

그러면서 새롭게 알게 된 사실, for문 범위를 range(변수의 길이)로 설정했다면 그 안에서 pop이나 append를 하면 인덱스 에러가 날 확률 99%이다는 것!!바로바로 수정해서 코드가 남아있지는 않은데 그러면서 공부한 내용을 아래 공부한 내용에 추가하겠다...

몇몇 테스트는 시간이 좀 걸려서 긴장했는데 통과!

 제출 답안 

from collections import deque

def solution(bridge_length, weight, truck_weights):
    second = 0 # 초
    amount = len(truck_weights) # 총 트럭 대수
    truck_weights = deque(truck_weights)
    on_bridge_weight = deque() # 다리 위에 있는 트럭들
    on_bridge_second = deque() # 트럭 진입 순서대로 다리 위에 있는 시간
    bridge_pass = [] # 다리를 지난 트럭
    
    while True:
        second += 1 # 1초 안에 일어나는 일들
        if len(on_bridge_weight) == 0: # 다리가 비어있으면
            on_bridge_weight.append(truck_weights.popleft()) # 첫 번째 트럭 올리기
            on_bridge_second.append(1) # 전진
        else: # 다리에 트럭이 하나라도 있으면
            index = 0
            while (index < len(on_bridge_weight)):
                index += 1
                if on_bridge_second[0] == bridge_length: # 다리 길이와 같아진 트럭이 있으면
                    bridge_pass.append(on_bridge_weight.popleft()) # 다 지난 트럭 리스트로 옮기기
                    on_bridge_second.popleft() # 시간 리스트에서도 빼주기
                    if len(bridge_pass) == amount: # 모든 트럭이 다리를 지나면
                        return second # 걸린 시간 반환

            for i in range(len(on_bridge_weight)): # 모든 트럭에 대해서
                if on_bridge_second[i] != bridge_length: # 다리 길이와 다르면
                    on_bridge_second[i] += 1 # 전진

            if len(truck_weights) != 0:
                if (sum(on_bridge_weight) + truck_weights[0] <= weight) and (len(on_bridge_weight) + 1 <= bridge_length): # 무게 총합과 길이가 넘지 않으면
                    on_bridge_weight.append(truck_weights.popleft()) # 트럭 하나 더 올리기
                    on_bridge_second.append(1) # 전진

 공부한 내용 

for문 안에서 pop()이나 append()를 사용하면 안 되는 이유

아래 예의 결과는 어떻게 될까.

a = [1,2,3,4,5]

for i, v in enumerate(a):
    if v < 5:
        a.pop(i)

enumerate()는 리스트의 인덱스를 함께 반환한다. 위에서 i가 인덱스넘버, v가 값이다. 5보다 작으면 해당 인덱스를 pop하라고 하니, 결과는 [5]일 것이다. 하지만 실제로 해보면 결과는 [2, 4, 5]다. 왜 그럴까?

 

왜냐면 pop은 즉각적으로 실행되기 때문이다.

즉, 첫번째 반복에서 1은 5보다 작기 때문에 pop(0)이 실행되고 리스트에서 바로 제거된다. 그 다음 반복은 2번 인덱스인데(i가 1), 이미 1이 꺼내어진 [2,3,4,5]의 반복이 되므로 v는 2가 아닌 3이 된다. 3이 pop되면 그 다음 인덱스에 해당하는 값은 5가 되는 것이다.

 

따라서 리스트를 반복시키면서 조건에 맞는 값을 pop 하겠다는 발상은 위험하다.

IndexError: deque(혹은 list) index out of range라는 오류를 마주하면 차라리 다행이지만 위의 경우처럼 그냥 잘못된 결과가 출력되면 잘못된 부분을 찾느라 머리가 아플 수 있다.

 

출처: https://butnotforme.tistory.com/entry/Python-for-%EC%95%88%EC%97%90%EC%84%9C-listpop%EC%9D%84-%EC%93%B0%EB%A9%B4-%EC%95%88%EB%90%98%EB%8A%94-%EC%9D%B4%EC%9C%A0

 다른 사람 답안 

다른 사람의 풀이 1

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    step = 0
    truck_weights.reverse()

    while truck_weights:
        total_weight -= bridge.popleft()
        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
        step += 1

    step += bridge_length

    return step

출처: 프로그래머스

처음에 이해가 안돼서 bridge를 단계별로 출력해보고 나서야 이해했다. 첫 번째 예제로 출력해보면 왼쪽과 같이 다리 길이만큼 0으로 채워진 deque를 만들고 while문 시작 시 맨 왼쪽 원소를 뺀 뒤

- 새로운 트럭을 올릴 수 없는 경우 0으로
- 새로운 트럭을 올릴 수 있는 경우 1로

채운다. 그리고 마지막 트럭이 빠져나올 시간(= 다리 길이)을 더해준다.

 

아이디어도 좋은데 실행시켜보니 내 코드보다 훠어어얼씬 빠르다. 다른 사람들의 코드들도 많이 실행시켜 봤는데 제일 빠른 것 같다. 이런 코드들 보다가 내 코드 보면 진짜 복잡하기 짝이 없지만... 지금의 나는 검색 없이 문제를 푼 것만으로도 칭찬해줘야겠다.

다른 사람의 풀이 2

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()

출처: 프로그래머스

클래스를 사용한 풀이, 이것도 내 코드보다는 월등히 빠른데 이해하기가 좀 어려웠다...

아직도 갈 길이 먼 초보 ㅠㅠ