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

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

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스

트럭을 세 그룹으로 나눠서 1. 지나간 트럭, 2. 다리 위 트럭, 3. 지나가지 않은 트럭 을 구분한다.

 

다리 위에 아무도없고 + 지나가지 않은 트럭도 없으면 => 끝. ( if len(brdg) ==0 and len(truck_weights)==0:)

 

 위의 탈출 조건을 두고, 다리 위의 트럭의 시간 배열을 따로 만들어 관리한다. brdgtime

While True로 loop을 돌고,

일단 시간 1씩 다 더해준다음에

brdgtime 이 가장 빠른(맨 앞) 의 트럭이 다리 길이와 같으면 앞에서부터 뺀다. 트럭이 1초에 1씩 간다고 가정했으니 가능함.

또한, 다리를 건너지 않은 트럭 중 선두 트럭 + 지금 다리위에 있는 트럭의 무게가 허용 무게보다 작으면 다리위에 선두 트럭 올려놓는다.

 

개인적으로는 탈출조건 이 중요하다 생각함. 

 

코드 1: pop(0) 때문에 느릴거라 예측함

python pop은 O(1)이지만 pop(i) 특정위치 pop은 O(N) 이기 때문이다. 

def solution(bridge_length, weight, truck_weights):
    answer = 0
    brdg = []
    brdgtime = []
    N = len(truck_weights)
    while True:

        if len(brdg) ==0 and len(truck_weights)==0:
            return answer


        for i in range(len(brdg)):
            brdgtime[i] += 1
        answer+=1

        if len(brdg)!=0:
            if brdgtime[0] == bridge_length:
                brdg.pop(0)
                brdgtime.pop(0)
        if len(truck_weights) !=0:
            if sum(brdg) + truck_weights[0] <=weight:
                brdg.append(truck_weights[0])
                brdgtime.append(0)
                truck_weights.pop(0)



    return answer

코드 2: deque사용

double-ended queue.

from collections import deque


def solution(bridge_length, weight, truck_weights):
    answer = 0
    brdg = deque()
    brdgtime = deque()
    truck_weights = deque(truck_weights)
    N = len(truck_weights)
    while True:

        if len(brdg) ==0 and len(truck_weights)==0:
            return answer


        for i in range(len(brdg)):
            brdgtime[i] += 1
        answer+=1

        if len(brdg)!=0:
            if brdgtime[0] == bridge_length:
                brdg.popleft()
                brdgtime.popleft()
        if len(truck_weights) !=0:
            if sum(brdg) + truck_weights[0] <=weight:
                brdg.append(truck_weights[0])
                brdgtime.append(0)
                truck_weights.popleft()



    return answer

 

 

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

제한 조건들이 너무 작아서 그런가. 10000^2 == 10^8 이니까  O(N^2) 를 써도 전부 1초내 통과가 가능한것 같다.

물론 내가 코딩을 잘못했을 가능성이 높다.