테스트 #2

두번째 문제 역시 혼자 힘으로 풀진 못했다. 그치만 언젠가 풀 수 있겠지! 역시 프로그래머스 레벨2 문제다.

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

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

역시 스택이나 큐를 이용하여 풀어야 하는 문제!
데크도 사용해볼 수 있겠다.

문제포인트 1 : 앞에 있는 트럭이 다리를 다 건너야 뒤에 있는 트럭도 건널 수 있다.
문제포인트 2 : 주어지는 배열은 다리길이, 최대하중, 트럭무게 3개이다.
문제포인트 3 : 1턴에 1초걸린다!
문제포인트 4 : 다리의 최대하중만큼의 트럭무게만 올라갈 수 있다.

1은 아까와 같이 스택/큐를 추천하는 거다.
2도 아까와 같이 와일문을 추천하는 거!
3은 시간카운트, 다 똑같지만
4 <- 얘가 까다롭다.
무게라는 제한이 하나 더 늘어서 논리가 복잡해졌다.

1) 스택을 이용한 풀이

https://orangebluestyle.tistory.com/21

전체코드

def solution(bridge_length, weight, truck_weights):

    stack = [0] * bridge_length
    time = 0
    bridge_weight = 0

    while stack:

        if stack[0] == 0:
            stack.pop(0)
            time += 1
        else:
            bridge_weight -= stack[0]
            stack.pop(0)
            time += 1

        if truck_weights:
            if bridge_weight + truck_weights[0] <= weight:
                bridge_weight += truck_weights[0]
                stack.append(truck_weights.pop(0))
            else:
                stack.append(0)
    return time

sum 함수로 풀면 5번테스트 케이스가 아슬아슬하게 통과되다가 안되다가 한다!
그러다 찾은 좋은 블로그 글이었다!

코드를 보면 빈 다리로 쓸 스택 [0, 0, 0, 0, 0, 0 ...] 이 있다!
리스트에 0을 넣고 *를 하면 쉽게 빈값이 채워진 배열을 만들 수 있다.

그리고 3개의 서로 연동해야 할 데이터를 담은 배열과,
새로 추가된 '다리의 현재무게'변수가 있다!

이 변수가 sum을 대신하여 들어감으로써 코드는 조금더 빨라진다.

코드의 흐름
stack이 다리가 된다.

와일문이 돌기 시작한다.
가장 먼저 걸리는 if문은 트럭무게가 있을때 = 트럭이 있을때 발동하는 두번째 if문이다.
만약 다리의 현재무게 + 배열의 첫번째 트럭의 무게가 최대하중보다 적다면
트럭무게는 다리의 현재무게에 더해지고 그 무게는 stack에 append된다!

그리고 첫번째 if문으로 돌아가면 이제 스택의 0번째는 0이 아니므로
첫번째 if문의 else가 발동된다!

다리의 현재무게를 현재 스택의 0번째에 append되어 있는 값만큼 빼주고 1초를 흘러가게 한다!
트럭이 지나갔다는 뜻이다.

이런식으로 트럭들을 최대하중만큼 꽉꽉 실어서 다리를 지나가게 하고!
마지막에는 stack에 걸린 값들을 전부 pop해주어서 확실히 빠져나가는거까지 시간을 잰다.

그리고 마지막으로 몇초가 흘러갔는지를 정답으로 제출해준다!

시간과 변수라니 정말 멋진 개념이다.

2) 데크를 이용한 풀이

여기에도 데크를 적용해 보았다!

전체코드

from collections import deque

def solution(bridge_length, weight, truck_weights):

    truck_weights = deque(truck_weights)
    stack = deque([0] * bridge_length)
    time = 0
    bridge_weight = 0

    while stack:

        if stack[0] == 0:
            stack.popleft()
            time += 1
        else:
            bridge_weight -= stack[0]
            stack.popleft()
            time += 1

        if truck_weights:
            if bridge_weight + truck_weights[0] <= weight:
                bridge_weight += truck_weights[0]
                stack.append(truck_weights.popleft())
            else:
                stack.append(0)
    return time

데크를 적용한 것 만으로 시간복잡도가 절반으로 줄었다!
정말 신기하다. 절반! 5번 케이스가 일반 팝은 200~300 나오는데
데크로 하면 60~110 나온다.

데크를 잘 쓰는 습관을 들이자!