[프로그래머스][C++] 다리를 지나는 트럭

다리를 지나는 트럭

문제 링크

다리를 지나는 트럭

분석

트럭이 다리를 지나는데 걸리는 시간은 bridge_length와 다리에 올라가는 시간으로, bridge_length + 1입니다.

트럭이 다리 위에 올라갈 수 있는 개수는 무게를 제외한다면 bridge_length만큼 입니다.

큐를 활용하는 문제입니다.

while문으로 다리의 크기만큼 트럭을 채우면서 다 찼을 경우 하나씩 빼는 방법으로 걸리는 시간을 계산했습니다.

풀이

#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    
    // 다리에 올라간 트럭 저장
    queue<int> bridge;
    // 현재 다리의 총 무게
    int totalWight = 0;
    
    // 지나가야하는 트럭
    for (int truck : truck_weights)
    {
        while (true)
        {
            // 걸린 시간
            ++answer;
            
            // 다리에 있을 수 있는 트럭이 꽉 찼다면 비워준다.
            if (bridge.size() == bridge_length)
            {
                totalWight -= bridge.front();
                bridge.pop();
            }
            
            // 트럭을 추가해도 되는지 확인
            if (totalWight + truck <= weight)
            {
                // 무게가 있는 트럭 추가
                totalWight += truck;
                bridge.push(truck);
                break;
            }
            else
            {
                // 무게가 0인 임시 트럭 추가
                bridge.push(0);
            }
        }
    }
    
    // 마지막 트럭이 나오는데 까지의 시간 계산
    answer += bridge_length;
    
    return answer;
}

이 방법의 실행 순서를 예를 들어, 설명해보겠습니다.

bridge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8

시간	다리 상태 (큐)	현재 다리 무게	진행 설명
1초	[7]	7	첫 번째 트럭(7)이 다리에 올라감
2초	[7, 0]	7	두 번째 트럭(4)은 다리에 올라갈 수 없어 0을 추가
3초	[0, 4]	4	7이 나가고, 4가 다리에 올라감
4초	[4, 5]	9	세 번째 트럭(5)이 다리에 올라감
5초	[5, 0]	5	4가 나가고, 다음 트럭(6)은 못 올라가므로 0 추가
6초	[0, 6]	6	5가 나가고, 6이 올라감

마지막 트럭이 다리에 올라가는 시점까지는 while문을 통해 시간이 증가하지만, 나오는 시간은 while문에서 계산되지 않으므로, 따로 계산해줍니다.

즉, 마지막 트럭 전까지 다리에 올라가는데 걸리는 총 시간을 반복문으로 구하고, 마지막 트럭이 지나가는 시간을 구합니다.

성능 요약

시간 복잡도는 $O(n \times m)$입니다.

• 트럭을 순회하는 반복문 $O(n)$
• 다리 길이에 무게가 있는 트럭이 추가될 때까지 반복하는 반복문 $O(m)$
• $O(n \times m)$

공간 복잡도는 $O(m)$입니다.

• 다리에 올라간 트럭을 저장하는 bridge $O(m)$

테스트 1 〉 통과 (0.01ms, 3.64MB)
테스트 2 〉 통과 (0.13ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.13MB)
테스트 4 〉 통과 (0.10ms, 4.14MB)
테스트 5 〉 통과 (1.07ms, 4.14MB)
테스트 6 〉 통과 (0.47ms, 4.2MB)
테스트 7 〉 통과 (0.02ms, 4.17MB)
테스트 8 〉 통과 (0.01ms, 4.17MB)
테스트 9 〉 통과 (0.05ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 4.21MB)
테스트 11 〉 통과 (0.01ms, 3.67MB)
테스트 12 〉 통과 (0.01ms, 3.68MB)
테스트 13 〉 통과 (0.02ms, 4.21MB)
테스트 14 〉 통과 (0.01ms, 3.63MB)