💻 다리를 지나는 트럭

분류 : Stack, Queue (스택, 큐)

사용 언어 : C++

문제 링크

🤔 문제 이해

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 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 이하입니다.

해결 방안

이 문제의 목표는 모든 트럭이 다리를 건너는 것이고 문제는 다리가 견딜 수 있는 무게의 한계가 있다는 것.

예시인 표에서 보이다시피 경과 시간, 건너고 있는 트럭, 아직 안 건넌 트럭을 저장해야 할 것이다.

이미 지나간 트럭은 체크할 필요가 없으니 없어도 될 것으로 판단된다.

트럭이 줄줄이 서 있고 맨 앞 트럭이 먼저 나가는 형태이므로 큐를 사용하는 것이 좋아 보인다.

💡 문제 풀이

방법 1 )

Queue를 사용하여 대기중인 트럭, 다리 위의 트럭을 직접 돌려본다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int result = 0;

    queue <int> truck_stand;    // 기다리는 트럭 queue
    queue <pair<int, int>> bridge;  // 다리 위에 있는 트럭 {트럭의 다리 위 위치, 트럭의 무게}
    int bridge_weights = 0; // 현재 다리가 들고 있는 무게

    for (int i = 0; i < truck_weights.size(); i++) {
        // 트럭들을 대기 queue에 넣어주기
        truck_stand.push(truck_weights[i]);
    }

    while (truck_stand.size() + bridge.size() != 0) {
        // "대기하고 있는 트럭 수 + 다리 위의 트럭 수"가 없을 때까지 반복
        if (truck_stand.size() > 0) {
            // 대기하고 있는 트럭이 한대라도 있을 경우
            if (bridge_weights + truck_stand.front() - ((bridge.front().first == bridge_length) ? bridge.front().second : 0) <= weight) {
                // 대기하고 있는 맨 앞 트럭이 다리 위로 올라가도 되는지 체크
                // 현 다리 무게 + 대기 중인 맨 앞 트럭 무게 - (만약 다리 위의 트럭이 다리 끝에 있어 나갈 수 있는지 체크)
                bridge.push({ 0, truck_stand.front() });    // 다리 위로 트럭을 올려주고 위치는 0
                bridge_weights += truck_stand.front();      // 다리 무게 더해주고
                truck_stand.pop();                          // 트럭 대기하던거 빼주고
            }
        }

        if (bridge.size() > 0) {
            // 만약 다리 위의 트럭이 있을 경우
            for (int i = 0, times = bridge.size(); i < times; i++) {
                // 트럭을 앞으로 옮겨주는 부분 
                // push와 pop을 한바퀴 돌려 1씩 증가하는 방법 사용
                bridge.push({ bridge.front().first + 1, bridge.front().second });
                bridge.pop();
            }

            result++;   // 시간++

            if (bridge.front().first > bridge_length) {
                // 다리 위 맨 앞의 트럭이 다리를 다 건넜을 시
                bridge_weights -= bridge.front().second;    // 다리 무게 제거해주고
                bridge.pop();                               // 트럭 제거
            }
        }
    }

    return result;
}

/*
정확성  테스트
    테스트 1 〉	통과 (0.05ms, 3.94MB)
    테스트 2 〉	통과 (0.57ms, 3.95MB)
    테스트 3 〉	통과 (0.01ms, 3.95MB)
    테스트 4 〉	통과 (3.84ms, 3.95MB)
    테스트 5 〉	통과 (24.09ms, 3.98MB)
    테스트 6 〉	통과 (10.63ms, 3.92MB)
    테스트 7 〉	통과 (0.04ms, 3.92MB)
    테스트 8 〉	통과 (0.02ms, 3.9MB)
    테스트 9 〉	통과 (0.19ms, 3.8MB)
    테스트 10 〉	통과 (0.02ms, 3.95MB)
    테스트 11 〉	통과 (0.01ms, 3.95MB)
    테스트 12 〉	통과 (0.02ms, 3.71MB)
    테스트 13 〉	통과 (0.05ms, 3.88MB)
    테스트 14 〉	통과 (0.01ms, 3.98MB)

채점 결과
    정확성: 100.0
    합계: 100.0 / 100.0
*/

시간 복잡도 : n * (bridge_length + 1)

대기 중인 트럭 Queue, 다리 위의 트럭 Queue를 만들고, 두 Queue의 Size 합이 0이 될 때까지 While 문 돌림.

한 타임 타임 다 돌리기 때문에 다리의 길이가 길수록 더 오래 걸리는 문제가 발생한다.

방법 2 )

트럭이 다리에 올라갈 수 있느냐 없느냐만 가지고 두가지로 나눠 코드를 작성.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int result = 0;

    queue <int> truck_stand;    // 기다리는 트럭 queue
    queue <pair<int, int>> bridge;  // 다리 위에 있는 트럭 {트럭의 다리 위 위치, 트럭의 무게}
    int bridge_weights = 0; // 현재 다리가 들고 있는 무게

    for (int i = 0; i < truck_weights.size(); i++) {
        // 트럭들을 대기 queue에 넣어주기
        truck_stand.push(truck_weights[i]);
    }

    while (truck_stand.size() + bridge.size() != 0) {
        // "대기하고 있는 트럭 수 + 다리 위의 트럭 수"가 없을 때까지 반복
        if (truck_stand.size() > 0 && bridge_weights + truck_stand.front() <= weight) {
            // 대기하고 있는 트럭이 한대라도 있고 대기하고 있는 맨 앞 트럭이 다리 위로 올라가도 되는지 체크
            bridge.push({ 0, truck_stand.front() });    // 다리 위로 트럭을 올려주고 위치는 0
            bridge_weights += truck_stand.front();      // 다리 무게 더해주고
            truck_stand.pop();                          // 트럭 대기하던거 빼주고

            for (int i = bridge.size(); i > 0; i--) {
                // 트럭을 앞으로 옮겨주는 부분 
                // push와 pop을 한바퀴 돌려 1씩 증가하는 방법 사용
                bridge.push({ bridge.front().first + 1, bridge.front().second });
                bridge.pop();
            }

            result++;   // 시간++

            if (bridge.front().first == bridge_length) {
                // 다리 위 맨 앞의 트럭이 다리를 다 건넜을 시
                bridge_weights -= bridge.front().second;    // 다리 무게 제거해주고
                bridge.pop();                               // 트럭 제거
            }
        }
        else {
            // 대기하고 있는 트럭이 없거나 대기하고 있는 맨 앞 트럭이 다리 위로 못 올라갈 시
            int time_flowing = bridge_length - bridge.front().first;    // 다리 위 맨 앞 트럭이 다리를 탈출하기까지 걸리는 시간

            // 다리 위 맨 앞 트럭은 어차피 탈출할 것이니 먼저 탈출시키기
            bridge_weights -= bridge.front().second;
            bridge.pop();

            for (int i = bridge.size(); i > 0; i--) {
                // 트럭을 앞으로 옮겨주는 부분 
                // push와 pop을 한바퀴 돌려 time_flowing 씩 증가
                bridge.push({ bridge.front().first + time_flowing, bridge.front().second });
                bridge.pop();
            }

            result += time_flowing; // 시간 += time_flowing 
        }
    }

    return result + 1; // 맨 마지막 트럭은 다리의 맨 끝 부분에 걸치게 되어 완전히 건너기 위해 + 1
}

/*
정확성  테스트
    테스트 1 〉	통과 (0.01ms, 3.92MB)
    테스트 2 〉	통과 (0.01ms, 3.95MB)
    테스트 3 〉	통과 (0.01ms, 3.9MB)
    테스트 4 〉	통과 (0.06ms, 3.94MB)
    테스트 5 〉	통과 (0.09ms, 3.96MB)
    테스트 6 〉	통과 (0.09ms, 3.96MB)
    테스트 7 〉	통과 (0.01ms, 3.95MB)
    테스트 8 〉	통과 (0.01ms, 3.96MB)
    테스트 9 〉	통과 (0.02ms, 3.96MB)
    테스트 10 〉	통과 (0.01ms, 3.97MB)
    테스트 11 〉	통과 (0.01ms, 3.89MB)
    테스트 12 〉	통과 (0.01ms, 3.95MB)
    테스트 13 〉	통과 (0.01ms, 3.93MB)
    테스트 14 〉	통과 (0.01ms, 3.94MB)

채점 결과
    정확성: 100.0
    합계: 100.0 / 100.0
*/

시간 복잡도 : 3n

방법 1과 달리 만약 트럭이 다리를 올라가지 못한다면 다리의 길이의 상관없이 한 번의 루프로 트럭을 탈출시켜 보다 빠른 성능을 보여준다.