Coding Test] 다리를 지나는 트럭 문제(Queue)

[Programmers School 문제 링크]

• Code

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 0;
    queue<pair<int, int>> bridge;   //Truck weight, Moved distance
    
    int idx_Truck = 0;
    while(true)
    {
        time++;           //시간 +1
        int cur_w = 0;    //다리 위에 있는 트럭들의 무게
        
        //현재 다리 위에 있는 트럭들 이동
        queue<pair<int, int>> cur;    //다리 위에 남은 트럭을 저장할 queue
        while(!bridge.empty())
        {
            //이동 후에도 건너는 중일 때
            if(++bridge.front().second <= bridge_length)
            {
                cur.push(bridge.front());      //트럭을 queue에 다시 추가
                cur_w += bridge.front().first; //현재 트력의 무게 더하기
            }
            //확인이 끝난 트럭 제거
            bridge.pop();
        }
        //다리에 남아있는 트럭 queue 복사
        bridge = cur;
        
        //모든 트럭이 출발하지 않음
        if(idx_Truck < truck_weights.size())
        {
            //다리 위에 트럭이 없거나 || 다음 트럭이 올라와도 다리가 버팀
            if(bridge.empty() || cur_w + truck_weights[idx_Truck] <= weight)
            {
                //다음 트럭 출발
                bridge.push(make_pair(truck_weights[idx_Truck++], 1));
            }
        }
        //모든 트럭이 출발함
        else
        {
            //모든 트럭이 다리를 지나면 반복문 종료
            if(bridge.empty())
                break;
        }
    }
    
    return time;
}

• 동작 흐름

1. 시간 +1

2. 현재 다리 위에 있는 트럭들 이동

3. 다음 트럭 출발 가능 검사

4. 모든 트럭이 다리를 지나가면 반복 종료

5. 모든 트럭이 지나가는데까지 지난 시간(time) 반환

위의 코드는 실제 동작에 문제는 없지만 시간이 1부터 모든 트럭이 지나는 순간 까지 반복하기 때문에 새로운 트럭이 진입하지 못하는 상황에서 앞의 트럭이 지나가는것을 무의미하게 일일히 검사한다.

• 개선 전 소요 시간

테스트 5의 경우 47.99ms까지 걸리기도 한다.

---

• Code (속도 개선)

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 0;
    queue<pair<int, int>> bridge;   //Truck weight, Moved distance
    
    int idx_Truck = 0;
    while(true)
    {
        time++;           //시간 +1
        int cur_w = 0;    //다리 위에 있는 트럭들의 무게
        
        //현재 다리 위에 있는 트럭들 이동
        queue<pair<int, int>> cur;    //다리 위에 남은 트럭을 저장할 queue
        while(!bridge.empty())
        {
            //이동 후에도 건너는 중일 때
            if(++bridge.front().second <= bridge_length)
            {
                cur.push(bridge.front());      //트럭을 queue에 다시 추가
                cur_w += bridge.front().first; //현재 트력의 무게 더하기
            }
            //확인이 끝난 트럭 제거
            bridge.pop();
        }
        //다리에 남아있는 트럭 queue 복사
        bridge = cur;
        
        //모든 트럭이 출발하지 않음
        if(idx_Truck < truck_weights.size())
        {
            //다리 위에 트럭이 없거나 || 다음 트럭이 올라와도 다리가 버팀
            if(bridge.empty() || cur_w + truck_weights[idx_Truck] <= weight)
            {
                //다음 트럭 출발
                bridge.push(make_pair(truck_weights[idx_Truck++], 1));
            }
            else //개선 부분 1
            {
                int left = bridge_length - bridge.front().second;
                queue<pair<int, int>> cur;
                while(!bridge.empty())
                {
                    bridge.front().second += left;
                    cur.push(bridge.front());
                    bridge.pop();
                }
                bridge = cur;
                time += left;
            }
        }
        //모든 트럭이 출발함
        else
        {
            //개선 부분 2
            time += bridge_length - bridge.back().second + 1;
            break;
        }
    }
    
    return time;
}

• 개선 부분 1

//첫 트럭이 다리를 벗어나기 직전까지 시간 이동
else
{
    //첫 트럭이 다리의 끝까지 가는데 남은 시간
    int left = bridge_length - bridge.front().second;

    //다리 위의 모든 트럭들의 시간 이동
    queue<pair<int, int>> cur;
    while(!bridge.empty())
    {
        bridge.front().second += left;
        cur.push(bridge.front());
        bridge.pop();
    }
    bridge = cur;

    //전체시간 이동
    time += left;
}

[개선 부분 1]의 else문에 진입 조건은 "더이상 새로운 트럭이 다리에 올라올 수 없다"이다.

그러므로 다리 위에 있는 첫 트럭이 완전히 지나가 무게를 줄이지 않으면 다음 트럭이 올라올 수 없다.

그렇다는 것은 첫 트럭이 다리를 건너는 순간까지 무게의 다리위의 트럭은 변하지 않기 때문에 첫 트럭이 지나갈때까지 매번 확인 하지 않고 첫 트럭이 지나가는 시간으로 이동하는 것으로 불필요한 연산을 하지 않아도 된다.

• 개선 부분 2

//모든 트럭이 출발함
else
{
    //마지막 트럭이 지나가는데 남은 시간(개선 부분)
    time += bridge_length - bridge.back().second + 1;
    break;
}

개선 목적과 방법은 [개선 부분 1]과 동일하다. 다만 첫 트럭이 아닌 마지막 트럭을 기준으로 한다.

트럭이 다리 길이보다 1 더 가야 다리를 지난것이기 때문에 +1을 해줘야한다.

• 개선 후 소요 시간

개선 전의 테스트 5의 경우 47.99ms가 걸렸지만 개선 후의 코드로는 0.23ms의 시간밖에 소요 되지 않는다.

---

• Queue를 사용한 이유

다리 위에 있는 트럭들을 알아내기 위해 큐(Queue)를 사용했는데 선입선출(FIFO)의 특징을 가진 큐를 사용하면 다리에 올라간 트럭의 순서를 직관적으로 확인하며 사용할 수 있으며, 일반 배열과 다르게 Index 관리를 하지 않아도 되어 편리하기 때문이다.