[코딩테스트] 프로그래머스 - 다리를 지나는 트럭 (Lv.2) in Python

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순서대로 건너며,

(순서 및 각 트럭의 무게는 매개변수 중 하나인 truck_weights배열에 주어집니다)

트럭은 1초에 1만큼 움직이고, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.

모든 트럭이 다리를 건너려면 몇 초가 걸리는가?

 

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

 

풀이

- 조금은 무식한(?) 방법으로 풀기로 결정했다.

- 제한 조건에 bridge_length, truck_weights모두 10,000이하라고 주어져서,

- 최악의 경우 - 주어진 시간에 트럭 한 대씩밖에 못 건너는 경우 - 에도,

필요한 시간은 bridge_length * truck_weights +1이고,

이는 보통 효용성 테스트에서 조건이 되는 1억에 딱 가까운 수이기 때문이다.

 

- 따라서, 나는 처음에 bridge_length * truck_weights + 1 길이의 배열을 0으로 초기화해주고, ... (A)

- 시간에 따라 다리를 지나는 트럭의 무게의 합을 배열에 집어넣기로 했다.

 

def solution(bridge_length, weight, truck_weights):
	#배열 초기화
    arr = [0] * bridge_length  * len(truck_weights) + [0]
    #다음 트럭이 지나갈 수 있는 처음 시간 index를 알기 위한 변수
    count = 0
    
    for x in truck_weights:
    	#현재 시간에 현재 트럭이 무게 초과로 못 올라가면,
        #올라갈 수 있는 시점이 될 때까지 count증가
        while arr[count] > weight - x:
            count += 1
        #올라갈 수 있는 시점이 되면, 현재 count부터 bridge_length만큼 현재 트럭 무게 추가
        arr[count:count+bridge_length] = [i + x for i in arr[count:count+bridge_length]]
        #시간은 여전히 가므로, 1초씩 증가
        count += 1
    
    answer = arr.index(0) + 1
        
    return answer

 

(A) 사실 파이썬 리스트의 크기는 가변적이기에, 코드를 조금 변형해주면 굳이 초기화 없이 구현이 가능할 것이다.

 

배열을 써서 상수시간 access가 가능해서 그런지, 효율성 테스트에서 그렇게 나쁘진 않았다!

 

다른 분들의 풀이

1. 

- 가장 따봉을 많이 받으신 분의 풀이가 class를 이용한 거여서 흥미로웠다!

읽어보면서 배웠다. 감사합니다, 똑똑하신 분들...

~> Bridge class 만듬

~> max_length, max_weight, queue (collections.dequeue), current_weight이 properties로 들어감

~> push method : current_weight + 다음 트럭의 무게 = next_weight

     : next_weight이 max_weight보다 작고 queue의 길이가 max_length보다 작으면,

     : 다음 트럭이 다리에 오를 수 있다는 의미니, queue에 다음 트럭을 append

     : current_weight =next_weight

     : 그렇지 않으면 False return.

~> pop method : queue.popleft()하고, pop된 만큼 current_weight에서 뻄

~> solution 함수

     : Bridge object 정의

     : truck_weights는 효율성 위해 dequeue로 만들어 줌

     : Bridge.queue를 bridge_length 길이로 초기화

     : Bridge.push가 가능하면 (True), 현재 트럭 push. 아니면 dummy_truck(0) push.

     : truck_weights의 모든 원소 push가 끝나면, count 증가.

 

클래스를 사용하지 않고 같은 로직으로 풀 수 있겠지만, OOP구성이 흥미로웠다.

 

2.

- 다른풀이는 bridge_length 길이의 dequeue를 만들고,

1초당 하나씩 앞에서 popleft()하면서 총 걸리는 시간을 잰 것이었다!