[C++/코딩테스트] 프로그래머스: 다리를 지나는 트럭

다리를 지나는 트럭 풀이

 

 

 

문제 설명

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

 

풀이 1

 

queue를 이용해 풀었습니다. 처음에는 q_bridge를 queue <pair>를 통해서 <트럭의 무게, 트럭의 위치>를 나타내려고 했습니다. 근데 queue의 접근자가 되지 않아서 그 부분에서 고민을 하다가 그냥 vector를 사용해서 해결하였습니다. 알고리즘의 순서를 간단히 표현하면 다음과 같습니다.

 

1. 버스의 무게들을 큐 변수(q_wait)에 대입합니다.

2. 처음 트럭을 다리로 보냅니다.

3. q_wait가 비어있을 때까지 반복문을 수행합니다.

   3-1. 트럭을 한 칸씩 이동시킵니다.

   3-2. 다리를 지난 트럭이 있는지 확인합니다.

   3-3. 대기해있는 트럭이 들어올 수 있는지 확인합니다.

4. 모든 트럭이 다리에 들어와 있으므로, 시간을 다리의 길이만큼 더하여 끝냅니다. 

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    vector <pair<int, int>> q_bridge;
    queue  <int>q_wait;
    for(int i=0; i<truck_weights.size(); i++)
    {
        q_wait.push(truck_weights[i]);
    }
    
    int time=1;
    int weight_now=0;
    int idx=0;
    weight_now+=q_wait.front();
    q_bridge.push_back(make_pair(q_wait.front(),1));
    q_wait.pop();
    
    while(!q_wait.empty())
    {
        time++;

        // 트럭 이동
        for(int i=idx; i<q_bridge.size(); i++)
        {
            q_bridge[i].second+=1;
        }
        
        // 다리를 지난 트럭 확인
        if(q_bridge[idx].second>bridge_length)
        {
            weight_now-=q_bridge[idx].first;
            idx++;
        }
        
        // 대기 트럭이 들어올 수 있는지 확인
        if(weight_now+q_wait.front()<=weight)
        {
            weight_now+=q_wait.front();
            q_bridge.push_back(make_pair(q_wait.front(),1));
            q_wait.pop();
        }
    }
    
    time+=bridge_length;
    answer=time;
    return answer;
}

 

풀이 2 (풀이 1 최적화)

앞에서는 벡터의 접근자를 활용해서 트럭의 위치를 정의했습니다. 하지만, 트럭의 위치의 접근자를 사용하지 않아도, 시간 변수를 활용하면 트럭의 위치 접근자를 활용하지 않아도 되는 것을 확인했습니다. 그리고 반복문 전에 첫 index 관련 코드가 불필요해서 제거했습니다.

그래서 수정한 내용은 요약하면 다음과 같습니다..

• vector<pair<int, int> q_bridge  → queue<pair<int, int> q_bridge
• 반복문 전에 초기 트럭 관련 코드 제거

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    queue <pair<int, int>> q_bridge;
    queue  <int>q_wait;
    for(int i=0; i<truck_weights.size(); i++)
    {
        q_wait.push(truck_weights[i]);
    }
    
    int time=1;
    int weight_now=q_wait.front();
    int idx=0;
    q_bridge.push(make_pair(q_wait.front(),1+time+bridge_length));
    q_wait.pop();
    
    while(!q_wait.empty())
    {
        time++;
        
        // 다리를 지난 트럭 확인
        if(q_bridge.front().second==time+1)
        {
            weight_now-=q_bridge.front().first;
            q_bridge.pop();
        }
        
        // 대기 트럭이 들어올 수 있는지 확인
        if(weight_now+q_wait.front()<=weight)
        {
            weight_now+=q_wait.front();
            q_bridge.push(make_pair(q_wait.front(),1+time+bridge_length));
            q_wait.pop();
        }
    }
    
    time+=bridge_length;
    answer=time;
    return answer;
}