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

• [ 장르 ] Queue
  [ Question ]

[#42583] 다리를 지나가는 트럭

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

programmers.co.kr

• My Code

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0,cur_Weight = 0,truck_Count;
    queue<int> Crossed;		// 지나간 트럭
    queue<int> Passing;		// 다리위에 트럭
    vector<int> waitBridge;	// 다리위 대기중인 각 트럭당 대기시간

    truck_Count = truck_weights.size();	// 초기 트럭수 변수에 저장
    while(true)
    {
        answer++;		// 단계 카운트
        if(!waitBridge.empty())	// 다리위에 트럭이 있으면
            for(auto iter = waitBridge.begin(); iter != waitBridge.end(); iter++)
                *iter -= 1;		// 다리위에 트럭큐에 끝까지 대기시간 -1감소

        while((!waitBridge.empty()) && waitBridge.front() == 0)	// 다리위에 트럭이있고, 다리끝까지 왔다면 ( == 대기시간 다 됬다면 )
        {
            Crossed.push(Passing.front());		// 현재 다리위에 맨 앞에 트럭, 다리를 건넜음큐에 push 
            cur_Weight -= Passing.front();		// 현재 다리위에 중량무게 이제 나갈 트럭무게만큼 차감 업데이트
            Passing.pop();						// 이제서야 다리위에 맨 앞 트럭 pop
            waitBridge.erase(waitBridge.begin());	// 대기시간 벡터도 맨앞에요소 하나삭제
        }
        if(Crossed.size() == truck_Count)	// 초기의 다리건너기전 트럭수랑, 건넌 트럭수 큐의원소의 수가 같으면 탈출
            break;
        if((!truck_weights.empty()) && weight >= cur_Weight + truck_weights.front())	// 매 단계마다, 다리를 건너기 전 트럭이 존재하고, 현재 다리위에 있는 트럭의 무게의 합과 지금 들어갈
        {																				// 트럭의 무게를 합한 것이, 다리의 하중보다 작거나 같다면 
            Passing.push(truck_weights.front());	// 다리위에 트럭추가
            cur_Weight += truck_weights.front();	// 추가된 트럭 무게만큼 총 무게 증가
            truck_weights.erase(truck_weights.begin());	// 다리건너기전 트럭원소는 삭제
            waitBridge.push_back(bridge_length);	// 새로 대기시간 (다리길이만큼) 벡터에 맨뒤에 삽입
        }
    }
    return answer;
}

 

" 지금까지 푼 것중엔 처음 알고리즘 답게 푼 것 같다. "
" queue 와 vector containner를 잘 사용하고, 로직도 나름 괜찮다. "
" ( 물론 더 최고의 방법이 있을 수 있겠지만....... ) " 

---

[ CheckPoint ]

• 문제를 풀다 마주친 첫번째 고민은, 다리위에 적재된 트럭마다 다리길이만큼 대기시간을 가지게되고, 각각 들어온 시점이 다를 수 있는데 이걸 어떻게 컨트롤 해야할까 ?
• 두번째 고민은, 오류에서 발견 됬는데, 다리위에 있던 트럭을 다리를 끝까지 다와서 건너간트럭큐에 push하거나, 다리에 적재되기전에 기존의 트럭 vector에 트럭을 다리위에 적재할때  vector에 트럭이 존재하는지를 먼저 체크를하고 뭔가를 해서 잘못된
  IndexError를 피할 수 있다.