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

<문제 설명>

 

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭 다리를 건너는 트럭 대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

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

<입출력 예>

bridge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

---

<내가 생각한 풀이>

 

다리를 정해진 순으로 건넌다는 것에 유의, 다리가 견디는 무게가 정해져 있기 때문에

다리의 무게를 체크하며 트럭이 순서대로 올라가야 한다!

 

코드 (일부 케이스에서 시간 초과)

# 한개의 테스트 케이스에서 시간초과 발생
def solution(bridge_length, weight, truck_weights):
    truck_weights = truck_weights[::-1]
    on_bridge=[0]*bridge_length
    time=0
    while truck_weights:
        time+=1
        on_bridge.pop(0)
        if sum(on_bridge)+truck_weights[-1]<=weight:
            on_bridge.append(truck_weights.pop())
        else:
            on_bridge.append(0)
    return time+bridge_length

truck_weights에서 값을 빼낼 때 맨 앞의 값부터 빼내기 때문에 [::-1]로 뒤집어줌

(pop()과정에서 pop(0)을 사용하지 않기 때문에 시간 복잡도를 줄일 수 있음)

 

on_bridge라는 다리상태를 보여주는 리스트, 시간을 체크할 time 변수 생성

 

truck_weights에서 모든 트럭이 다 다리로 올라갈 때까지 반복문이 돌게 함

 

트럭이 다리에 올라가서 1초에 1만큼 지나고 있기 때문에 반복문이 돌 때마다 time 변수는 1씩 증가

 

그리고 반복문이 돌때마다 다리 위 상태가 계속 변하기 때문에 리스트가 변하는 과정이 반복됨

(FIFO 선입선출 구조를 생각하면 됨, 다리를 다 지난 값은 빠져나가고 맨뒤로는 값이 계속 들어가고!)

 

time변수는 마지막 트럭이 다리를 다 지나기까지의 시간은 아님!

(while문이 마지막 트럭까지 다리에 오르게 되면 완료되기 때문에)

따라서 return 값은 time+bridge-length(다리 길이)를 해주면 됨

 

전반적인 풀이는 맞았지만 시간을 줄여야 하는 상황이었음!

 

수정 코드

'''
sum 함수를 대체하여 on_bridge_weight이라는 변수 생성
다리 위 무게를 체크하도록 함! 
-> 시간복잡도 줄임
'''

def solution(bridge_length, weight, truck_weights):
    truck_weights = truck_weights[::-1]
    on_bridge = [0]*bridge_length
    time = 0
    on_bridge_weight = 0
    while truck_weights:
        time+=1
        out = on_bridge.pop(0)
        if out != 0:
            on_bridge_weight -= out
        if on_bridge_weight+truck_weights[-1]<=weight:
            go_in = truck_weights.pop()
            on_bridge.append(go_in)
            if go_in != 0:
                on_bridge_weight += go_in
        else:
            on_bridge.append(0)
    return time+bridge_length

수정 전 코드에서 다리위의 무게를 체크하기 위해 sum()함수를 사용했는데,

sum함수가 수행될 때 리스트의 모든 값을 방문하는 O(n)의 시간복잡도를 갖게된다.

sum함수만 대체해도 시간 단축을 도울 수 있다고 생각했다.

 

다리위 무게를 체크하기 위해서, on_bridge_weight이라는 변수의 값을 증감 시키기로 했다.

out 이라는 변수는 다리를 통과해서 나가는 값, go_in은 다리에 들어가는 값이다.

두 값이 0이 아닐 경우 out은 -, go_in은 +

 

이렇게 해서 모든 케이스를 통과하는 코드를 작성했다 ㅇㅅㅇ

 

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

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