프로그래머스 Lv.2 다리를 지나는 트럭

문제 링크

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

 

풀이

before: 다리를 건너기 전 트럭

before의 원소: 트럭의 무게

bridge: 다리를 건너는 트럭

bridge의 원소: [트럭의 무게, 트럭이 다리에 처음 나타난 시간]

after: 다리를 건넌 후 트럭

after의 원소: 트럭의 무게

 

time: 경과 시간

 

length: 트럭의 총 개수

 

    before = truck_weights[:]
    bridge = []
    after = []
    time = 0
    length = len(truck_weights)

 

 

예시)

bridge_length: 2

weight: 10

truck weights: [7,4,5,6]

다리에 최대 2대까지 가능

다리 최대 무게 10kg

초	다리를 건넌 후 트럭				다리를 건너는 트럭		다리를 건너기 전 트럭
0							7	4	5	6
1						7	4	5	6
2					7		4	5	6
3				7		4	5	6
4				7	4	5	6
5			7	4	5		6
6		7	4	5		6
7		7	4	5	6
8	7	4	5	6

 

다리를 건너는 과정

1. after ← bridge

다리에 트럭이 있다면 

그리고 트럭이 다리에 있는 시간이 bridge_length초 이상 경과한다면

1) 다리에서 맨 처음에 있는 트럭을 제거하고 그 트럭을 저장한다.

   = bridge의 맨 처음 원소를 pop한다.

2) 다리를 건넌 후 트럭에 새로 추가한다.

   = after의 맨 마지막 원소로 append한다.

        if len(bridge) > 0:
            if time -bridge[0][1] >= bridge_length:
                item2 = bridge.pop(0)
                after.append(item2[0])

 

 

2. bridge ← before

다리를 건너지 않은 트럭이 있다면

다리에 있는 트럭들의 총 무게(s)를 계산한다.

다리에 있는 트럭들의 총 무게(s)와 다리를 건너고자 하는 트럭의 무게(before[0])의 합이 다리가 견딜 수 있는 무게(weight) 이하라면

(= s + before[0] ≤ weight)

1) 다리를 건너기 전의 맨 앞 트럭을 제거한다.

   = before의 맨 처음 원소를 pop한다.

2) 다리를 건너는 트럭에 새로 추가한다.

    이 때 트럭의 무게와 현재 경과 시간을 같이 추가한다.

   = bridge의 맨 마지막 원소로 append한다.

        if len(before) > 0:
            s = 0
            for b in bridge:
                s += b[0]
            if s + before[0] <= weight:
                item1 = before.pop(0)
                bridge.append([item1,time])

 

3. 해당 경과시간을 1초씩 추가한다.

        time += 1

 

4. 이 과정은 다리를 건넌 후의 트럭의 수가 전체 트럭의 수랑 같아질 때까지 계속 이어진다.

    while len(after) < length:

 

다리를 건너는 과정의 전체 코드

    while len(after) < length:
        if len(bridge) > 0:
            if time -bridge[0][1] >= bridge_length:
                item2 = bridge.pop(0)
                after.append(item2[0])
                
        if len(before) > 0:
            s = 0
            for b in bridge:
                s += b[0]
            if s + before[0] <= weight:
                item1 = before.pop(0)
                bridge.append([item1,time])
                
        time += 1

 

트럭이 다리를 모두 건넌 후

트럭이 다리를 전부 다 건너는데 소요된 시간을 return한다.

    return time

 

전체 코드

def solution(bridge_length, weight, truck_weights):
    before = truck_weights[:]
    bridge = []
    after = []
    time = 0
    length = len(truck_weights)
    
    while len(after) < length:
        if len(bridge) > 0:
            if time -bridge[0][1] >= bridge_length:
                item2 = bridge.pop(0)
                after.append(item2[0])
                
        if len(before) > 0:
            s = 0
            for b in bridge:
                s += b[0]
            if s + before[0] <= weight:
                item1 = before.pop(0)
                bridge.append([item1,time])
                
        time += 1
        
    return time