풀이전략

• 먼저 들어간 친구가 먼저 나오는 방식이어서 큐를 사용해야겠다고 생각함.

1번째 풀이)

대키 트럭과 카운트값을 pair형식으로 가지고 진행하면서
카운트값이 bridge_length가 되면 pop하는 방식으로 진행하려고 했다.
pair로 가지고 있으려면 vector를 사용한다.
문제점으로는 앞에 vector의 앞에 있는 것을 erase해야 하므로 시간복잡도가
낮아지지 않을까? 생각을 함.

=> 문제에서는 무관하지만, 만약에 다른 방법이 떠오르지 않는다면 이 풀이방법으로 접근하자. 부분점수라도 맞아야한다!
덧붙여서 프로그래머스 문제 풀어보면 erase를 쓰더라도 효율이 막 떨어지지는 않는다. 그러므로 erase를 해야되는 풀이 전략밖에 생각이 안나면 erase로 일단 풀고, 효율성이 떨어진다면, 다른 전략을 고안해내자.

소스코드

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

//01:15
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    
    vector<pair<int,int>>v;
    //큐는 인덱스 접근 못하므로 ,, 무한 반복문 처리하는 조건으로 추가함.
    queue<int>q;    
    int sum = 0;
    
    for(int i = 0; i< truck_weights.size(); i++)
    {
        q.push(truck_weights[i]);
    }    
    
    while(1)
    {
        answer++;
        if(weight >= sum + q.front() && !q.empty())
        {
            sum += q.front();   
            v.push_back({q.front(), 0});
            q.pop();
        }
        
        for(auto& i : v)
        {
            i.second += 1;
        }
        
        if(v[0].second == bridge_length)
        {
            sum -= v[0].first;
            v.erase(v.begin());            
        }
        
        if(v.empty() && q.empty())
            break;
    }
    
    
    return answer + 1;
}

효율성 테스트

2번째 풀이 : 구글링을 통해 접근하는 방법을 새롭게 배웠다.

: 나는 생각하지 못했지만, 버스 한대가 다리를 완전히 지나가는 데에는
bridge_length만큼이 지나면 다리를 통과하는 것이다.

bridge_length와 비교할 수 있는 것은!! q의 size로 비교를 하면된다.
하지만, 예를 보면 limit이 10이고, 7의 경우는 2초동안 다리 위를 혼자 있어야하는데, q의 사이즈를 늘릴 것인가에 대한 생각을 하면???

만약에 7 < limit과 같은 상황이 온다면
큐에 빈버스 즉 0을 집어넣는 방식으로 진행 할수 있다.

효율성 테스트 및 교훈

-> 위에 보다 약간 좋아졌지만, 내 생각에는 erase를 사용하지 않기 때문에 훨씬 좋은것 같다. 하지만, 내가 이 부분을 캐치하지 못했다.

소스코드

: while문 조건식 끝마칠때 생각해내기 어려울 수 있다.

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    
    queue<int>q;
    int sum = 0;
    int index = 0;
    
    while(1)
    {
        answer++;

        if(q.size() == bridge_length)
        {
            sum -= q.front();
            pass[index - 1] = q.front();
            q.pop();
        }
        
        //이런식으로 마치면 6이 추가되자마자 끝나게 되므로, 밑에 조건식으로 진행해야 한다. 
        //그런데 생각해내기가 어렵다.
        //if(index == truck_weights.size() - 1)
        //{            
        //    break;
        //}
        
        if(sum + truck_weights[index] <= weight)
        {
            //코드 상으로 봤을때 추가적으로 마지막 트럭 추가 시에 
            //마지막 트럭이 지나가는 거리만큼 추가 후에 종료하는 구문이다. 
            //여기 생각해내기 어려울 수  있다. 
            //이 조건문을 위에다가 써주면 
            if(index == truck_weights.size() - 1)
            {
                answer += bridge_length;
                break;
            }
                                   
            sum += truck_weights[index];
            q.push(truck_weights[index]);
            index++;
        }
        else
        {
            q.push(0);
        }
             
    }
    
    return answer;
}