다리를 지나는 트럭 python - [프로그래머스/스택/큐 알고리즘]

문제 내용 요약

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

 

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

따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.

문제 원리파악

일단 문제를 읽으면서 발견할 수 있는 조건들을 정리한다.

0) 다리를 지나는 트럭의 큐 길이가 트럭의 총 갯수와 같아지면 반복문 종료

1) 1초당 다리를 건너는 트럭의 위치는 1씩 증가함
     즉,  bridge_length가 2이면 1초때 건너는 트럭은 1~2초에 건너고 3초에는 이미 건너는 시점임

2) 다리를 건널 때 얼만큼 다리를 지난지를 알기위한 큐가 필요함

3) 1)의 조건을 고려하여 다리를 건너는 트럭은 현재 경과시간 + 다리 길이만큼의 n초동안 건너면 지나간 트럭 큐로 빼줘야함

4) 다리를 건너는 트럭 큐의 합과 다음 대기트럭의 무게합이 weight보다 낮으면 다리를 건너는 트럭큐에 추가가능

 

Tip)

문제 풀다가 내가 시행착오를 겪었던 부분이 반복문 속에서 최초로 한번만 수행해야하는 조건이 예외적으로 필요한 부분도 있다.

그리고 리스트보단 큐나 힙을 써서 풀 수 있으면 큐나 힙을 쓰자, 리스트는 속도에서 걸리는 경우가 많더라..

 

문제풀이

문제를 풀어보다가 아래의 여러 조건들의 #1, #2, #3, #4의 순서를 어떻게 잘 설계해서 코드를 짜냐가 중요하다.

처음에는 일단 조건들을 먼저 코드로 구현하다 순서가 꼬여버려서 더 헷갈렸다. 차근차근 뭐를 뭔저 진행해야하는지 설계하고 짜는것이 중요하다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    
    queue = deque(truck_weights)
    bridge_queue = deque()
    end_queue = deque()
    
    
    length = len(truck_weights)
    
    
    # count_list는 트럭이 다리를 지나가면서 위치를 저장해주는 큐 
    time = 0
    count_list = deque()
    
    # 다리를 지나는 트럭의 큐 길이가 트럭의 총 갯수와 같아지면 반복문 종료
    while len(end_queue) < length:
        
        
        #1 현재 시간을 가장먼저 늘려줌 
        time += 1
        
        # 다리를 건너는 트럭의 큐가 비어있을 경우 최초수행후 continue
        if not bridge_queue:
            bridge_queue.append(queue.popleft())
            count_list.append(1)
            continue
       
        #2 다리를 건너는 트럭의 위치를 1씩 이동시킴 
        for i in range(len(count_list)):
            val = count_list.popleft() + 1
            count_list.append(val)
        
        #3 다리의 맨앞 트럭의 위치가 다리길이보다 높을경우 다리를 지난 것으로 판단해 pop / 이외에는 다시 다리위치 큐에 append  
        va1 = count_list.popleft()
        if va1 > bridge_length:
            end_queue.append(bridge_queue.popleft())
        else:
            count_list.appendleft(va1)
        
        #4 만약 대기트럭의 큐에 값이 존재할 경우만 대소비교 조건 실행, 즉 대기트럭이 다 건너고 다리를 건너고 있을 경우에는 수행하지 않음
        if queue:
            val2 = queue.popleft()
            
            # 현재 건너는 트럭무게의 합과 맨 앞의 대기트럭의 합을 weight와 비교하여 대기트럭이 다리를 건널 수 있는지 업는지 비교
            if sum(bridge_queue) + val2 <= weight:
                bridge_queue.append(val2)
                count_list.append(1)
                
            elif sum(bridge_queue) + val2 > weight:
                queue.appendleft(val2)
            
    answer = time
    return answer


solution(2, 10, [7,4,5,6])

깨달은점

역시나 코딩테스트 문제를 풀때도 어떻게 설계하느냐가 중요했다. 해당 문제를 구현할 때 어떤게 먼저진행되야 하고, while반복문 안에서도 if를 어떻게 잘 쓰냐에 따라서 문제에 대한 정답을 찾아냈다. 그리고 힙과 큐를 사용하여 풀 수 있는 문제는 되도록이면 리스트말고 힙과 큐를 사용하자.