[프로그래머스, C++] 다리를 지나는 트럭(스택/큐 파트)

문제 링크

코딩테스트 연습 - 다리를 지나는 트럭

 

 

 

풀이

처음에 무작정 배열로 풀다가 고생했다.

 

해결방법은

그리고 (시작시간+다리 길이)가 해당 트럭이 빠져나오는 시간인 것을 파악하고

다리가 순서대로 빠져나오므로 Queue문제인것은 확실해서 여러 조건문을 달고 정리하여 해결했다.

 

조건은 다음과 같이 나눌 수 있다.

1) 다리가 비어있을 경우(트럭을 무조건 올릴 경우)

2) 다리가 비어있지 않을 경우

    2.1) 트럭이 빠져나올 수 있는 경우

        2.1.1) 트럭을 올릴 수 있는 경우

        (현재 다리에 있는 트럭의 무게 + 올릴 트럭 무게가 다리의 최대 버티는 무게 이하일 경우)

 

        2.1.2) 트럭을 못올리는 경우

    2.2) 트럭이 못빠져나오는 경우

        2.2.1) 트럭을 올릴 수 있는 경우

        (현재 다리에 있는 트럭의 무게 + 올릴 트럭 무게가 다리의 최대 버티는 무게 이하일 경우)

 

        2.2.2) 트럭을 못올리는 경우

 

이를 if(), else if() 로 정리하면...

1) if(트럭을 무조건 올리는 경우 = 다리가 비어있을 경우)  --- answer++; 시간 경과

2.1) if(트럭이 빠져나오는 경우) --- 못올리는 경우랑 중복되므로 answer++;을 하지 않는다.

2.a) if(트럭을 못올리는 경우) ---- answer++; 시간 경과

2.b) else if(트럭을 올릴 수 있는 경우) ---- answer++; 시간 경과

 

로 나눌 수 있다.

 

올릴 트럭 개수만큼 반복문을 돌면서

{

    if(다리가 비어있을 경우) 밑에 skip! - 트럭을 올렸기 때문에

    while(true)

    {

        if(2.1)

        if(2.a)

        else if(2.b) : 트럭을 올리면 break;

    }

    // 이곳의 answer는 해당 index 트럭이 올라간 시점을 가리킨다(다리가 비어있을 경우 제외!)

}

 

마지막에는 answer는 마지막 트럭의 올린 시점을 기록했으므로 answer + bridge_length를 return한다.

 

참고로, 트럭을 못올리는 경우에 일부러 push(0)으로 다리 무게에 변화가 없도록 하였다.

 

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

using namespace std;

// 다리 길이 bridge_length
// 무게 weight
// 대기 트럭의 각 무게 truck_weights

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;     // 트럭이 올라간 시점
    
    // process
    queue<int> q;
    int sum=0;      // 다리에 올라간 총 무게
    for(auto e: truck_weights){     // 모든 트럭이 올라갈 때까지
        if(q.empty()){      // 다리가 비어있을 경우 넣기
            q.push(e);
            sum+=e;
            answer++;
            continue;		// 트럭을 올렸으니 밑에는 Skip
        }
        while(true){
            if(q.size()==bridge_length){       // 트럭이 빠져나올 경우
                sum -= q.front();
                q.pop();
            }
            if(sum + e > weight){          // 트럭을 못올리는 경우
                q.push(0);
                answer++;
            }
            else if(sum + e <= weight){         // 트럭을 올리는 경우
                q.push(e);
                sum += e;
                answer++;
                break;
            }
            
        }
        // cout<<answer<<endl;     // 트럭이 올라간 시점
    }
    answer += bridge_length;        // 마지막 트럭이 올라간 시점 + 다리 길이 = 완전히 통과한 시간
    
    return answer;      // 모든 트럭이 다리를 건너는 최소 시간 리턴
}