스택 - 다리건너기 문제

이번 포스팅은 입력 순서가 정해진 트럭의 다리건너기 입니다.

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

코딩테스트 연습 - 다리를 지나는 트럭

해당 문제의 추상화된 이미지는 아래와 같다고 볼수있습니다.

 

추상화된 해당 문제

이번 문제를 살펴보면

1. Truck은 처음 정해진 순서로만 다리에 진입할 수 있다.

2. 한번에 두대 이상의 Truck이 동시에 다리로 진입할 수는 없다.

3. 다리의 하중을 넘게 Truck이 다리위에 올라가진 못한다.

 

문제는 일반적인 시뮬레이션에서 배우는 단일창구 문제의 응용형 문제입니다.

 

해당 문제의 풀이는 두가지로 가능합니다.

1. 반복문을 통해서 1초마다의 상황을 시뮬레이션(액티비티 중심 모델링)

2. Truck이 Bridge에 들어옴 or 나감 Event가 발생할 때 마다 상황을 판단(사건 중심 모델링)

 

1번 시뮬레이션 방법은 직관적 이지만, 계산이 필요없는 시간에도 반복문이 돌게 됩니다.

 

때문에 사건중심 모델링 대비 코드실행에 많은 시간이 걸립니다.

 

2번 방법론은 설계가 어렵고, 시뮬레이션 중간 과정을 확인하기 어렵다는 단점이 있지만

 

1번 방법론 대비 확실히 빠릅니다!(불필요한 반복문 실행X)

 

일단, 이번 포스팅은 1번 방법론으로 작성된 해당 문제의 해답입니다 :)

def solution(bridge_length, weight, truck_weights):
    answer = 0            
    #첫번째는 Truck의 경과시간, 두번째는 해당 Truck의 무게
    timer = [[],[]]    
    #도착한 트럭의 수를 count합니다.
    end = 0
    #초기 트럭의 수를 count하여 도착한 한 트럭의 목표치로 사용합니다.
    init_truck_count = len(truck_weights)
    #1초 간격으로 time을 증가시키는 방법을 사용
    while True:        
        #처음에 아무것도 없는 상태일 경우는 pass
        if len(timer[0]) == 0:
            pass
        #bridge를 다 건넌 트럭이 있는지를 확인합니다.
        #1초간격으로 time이 증가하기 때문에, 가장 앞에있는 트럭의 시간과
        #bridge_length를 비교해줍니다.
        elif timer[0][0]>=bridge_length:
            #도착한 트럭이 있으면 bridge의 여유무게를 복원하고
            #해당 트럭에 대한 정보를 timer에서 제거하고 도착한 트럭의 count를 증가
            weight = weight + timer[1].pop(0)
            timer[0].pop(0)         
            end = end +1
        #아직 시작지점에 트럭이 남아있는지 확인합니다.
        if len(truck_weights)!=0:
            #이때 가용 weight와 다음 순서의 트럭의 무게를 비교하여, 추가 여부를 결정합니다.
            if weight - truck_weights[0]>=0:
                #timer에 트럭의 무게와, 트럭의 운전 시간을 추가해줍니다.
                timer[0] = timer[0] + [0]
                temp = truck_weights.pop(0)
                timer[1] = timer[1] + [temp]
                #마지막으로 bridge의 가용 weight를 갱신합니다.
                weight = weight - temp                

        #트럭의 bridge위에서 운전 시간을 갱신
        for i in range(len(timer[0])):
            timer[0][i] = timer[0][i] + 1
        #총 소요시간을 갱신
        answer = answer + 1
        #처음 있던 트럭이 모두 도착하면 반복문을 종료 후 소요시간을 반환
        if end == init_truck_count:
            break
            
    return answer

solution(2, 10, [7, 4, 5, 6])
#총 8초의 소요시간이 발생
Out[17]: 8