[프로그래머스 스택/큐]다리를 건너는 트럭 - Python3

문제

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

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

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 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):
    # 시점
    time = 0
    
    # 다리를 지나고 있는 트럭
    passing = []
    
    # 다리를 다 건넌 트럭
    passed = []

    # 대기하고 있는 트럭이 없을 때까지 반복한다. 
    while truck_weights:
        # 시점을 1 더한다. 
        time += 1
        print("\n-----현재 시점은", time, "입니다-------")

        # 한번 반복하는 동안(한 시점에서 다음 시점으로 가는 동안), 다리를 건너고 있는 버스가 도착하는 것을 구현했다.
        # 다리를 건너고 있는 버스가 있다면,
        if passing:
            for i in range(len(passing)):
                # passing[i][1]의 값을 1 빼준다. passing[i][1]의 값은, 버스가 다리를 건너기 시작한 시점부터 부여받은 bridge_lenth이다
                # 즉, 다리를 건너기까지 남은 시간이 매 시점이 지날때마다 1씩 감소하는 것이다. 
                passing[i][1] -= 1
                print("무게 " + str(passing[i][0]) + "인 버스 가는중, 버스 정보: " , "버스 무게: ", passing[i][0], "남은 시간: ", passing[i][1])

        # 그렇게 1초가 지나고, 버스가 도착하기 까지 남은 시간이 0이라면 그 버스는 도착한 것이다.
        # passing배열을 순회하면서, 
        if passing:
            print('남은 시간: ', passing[0][1])
            # 가장 먼저 passing배열에 추가된 원소의 첫번째 값이 0이라면 그 원소를 pop해서, passed배열의 원소로 append한다. 
            if passing[0][1] == 0:
                print("버스가 도착했습니다")
                print("도착한 버스 무게: ", passing[0][0])
                passed.append(passing.pop(0))
                print("도착한 버스들 목록: ", passed)

        # 버스 출발
        print("\n대기중인 버스 출발여부 판단하겠습니다")
        print("대기중인 버스 무게: ", truck_weights[0])

        # 현재 다리의 무게를 구하기 위한 변수 current_weight
        current_weight = 0
        for i in range(len(passing)):
            current_weight += passing[i][0]
        print("currnet_weight: ", current_weight)

        # 현재 다리를 지나고 있는 버스의 무게와, 대기중인 첫 번째 버스의 무게를 더한 값을 다리가 지탱할 수 있는 무게와 비교한다
        # 만약 두 값을 더한 값이 다리의 최대 무게보다 작다면
        if current_weight + truck_weights[0] <= weight:
            # 대기중인 배열의 원소를 하나 빼고, 건너는 시간을 나타내는 bridge_length값을 포함한 배열 형태를 passing에 append한다.
            passing.append([truck_weights.pop(0), bridge_length])
            print("무게", passing[0][0], "인 버스 출발합니다")
        # 두 값을 더한 값이 다리의 최대 무게보다 작다면 대기중인 버스는 출발하지 못한다. 
        else:
            print("무게 초과로 버스 출발 안함")

        print("---------"+str(time)+"초 시점 종료-------------")
        
        # 마지막 버스가 출발한 시점부터, 도착하기 까지 걸리는 시간인 bridge_length를 더해서 리턴한다
    return time + bridge_length
    
    
    
bridge_length = 100
weight = 100
truck_weights = [10,10,10,10,10,10,10,10,10,10]
print("정답: ", solution(bridge_length, weight, truck_weights))

 

설명

이 문제를 풀면서 사용한 자료구조는 리스트이다. 큐를 잘 알았더라면 좋았겠지만, 리스트도 활용하기에 따라 큐처럼 쓸 수 있으므로 리스트를 사용하였다. 

• passing[]: 현재 다리를 지나고 있는 트럭의 정보를 담은 배열이다. 각 원소들은 [트럭의 무게, 도착까지 남은 시간]형태이다. 
• passed[]: 다리를 건넌 트럭들의 정보를 담은 배열이다.
• truck_weights[]: 문제에서 입력으로 주어지는 배열이다.

문제를 고민하다가, 한 시점마다 해야할 일을 정해주기로 했다. 위 코드에도 나와있듯이, 한 시점이 지날때마다 확인해야 하는 것은 다음과 같다. 

1. 다리 위를 지나고 있는 트럭이 도착하기까지 남은 시간을 1씩 뺀다.
2. 남은 시간을 1 뺐는데, 그 남은 시간이 0이라면 그 트럭을 도착한 것으로 간주한다.
3. 대기 중인 트럭이 출발할 수 있는지 판단하고, 기준에 부합한다면 출발해야 한다. 

위의 제약 사항들을 아래와 같이 구현하였다.

1. -> passing배열을 순회하면서 passing[i][1] 을 1 감소시키는 것으로 구현
2. -> passing배열에서 0번째 원소를 pop하고, pop한 원소를 passed배열에 append하는 것으로 구현
3. -> passing배열을 순회하면서 모든 무게를 더하고, 대기중인 트럭의 무게까지 더해서 weight보다 작으면 trucks_weight에서 pop한 후 passing배열에 [트럭의 무게, bridge_length]형태로 append, 아니면 대기하는 것으로 구현

 

결과

후기

내가 풀어본 문제중에 좀 복잡한 문제였다. 생각을 정리하느라 쓴 공책 종이가 네다섯장은 되는듯 하다. 아직 초보인지라 어떻게 접근해야 할 지를 감을 못잡아아서, 최대한 차근차근 구현했다. 처음에는 버스가 조건에 맞게 출발하는지, 배열들은 출발에 따른 동작을 올바르게 하는지 구현했다. 그 다음에는 버스가 가고있는 것을 구현했고, 그 다음에 버스가 도착하는 것을 구현했다. 이렇게 해야 할 일들을 말로 풀어서 크게크게 쪼개놓고, 그것을 더 쪼개서 해당하는 동작들을 정의한 다음에야 코드가 써졌다. 아주아주 좋은 경험이었다. 바로 이맛이야 캬하하하하~~~~