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

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

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

 

스택/ 큐 문제이다.

 

선입선출방식을 기본으로 하는 자료구조인 큐를 사용해서 풀면 된다.

[ 풀이 ]

1. 초기화를 해준다.

초기 다리 큐를 다리 길이만큼 0으로 초기화해준다.

여기서 다리길이는 2이다. 다리 위에 있는 차의 무게 (cur_weight) 또한 0으로 초기화.

그리고 다리위에 있는 차의 개수(cur_cnt)도 0으로 초기화해준다.

0

0

2. 맨 앞의 큐를 pop 해준다.

2-1. pop 한 value 가 0 일 경우

그냥 차들을 한칸씩 이동시킨 것이기 때문에 아무런 변화를 주지 않는다.

0

2-2. pop 한 value 가 0 이 아닐 경우

차가 나온 것이므로 cur_weight -= value;  cur_cnt--; 를 해준다.

0

7

0

3. 타겟 트럭이 다리에 들어갈 수 있는지 판별한다.

3-1. 타겟 트럭이 다리에 들어갈 수 있을 경우

예시의 첫번째 트럭인 7 이 이와 같은 경우이다.

타깃 무게 + cur_weight  < weight이고 cur_cnt+1 < bridge_length 이므로 다리에 들어갈 수 있다.

따라서 q 에 push 해주고

cur_weight를 타깃 무게+cur_weight로 업데이트해주고, cur_cnt를 ++ 해줘서 차가 다리 위에 들어왔다는 것을 업데이트해준다.

2.로 돌아간다.

7

0

3-2. 타깃 트럭이 다리에 들어갈 수 없을 경우

이 경우 예시의 두 번째 트럭인 4와 같은 경우이다.

타깃 무게 + cur_weight > weight 이기 때문에 다리에 올릴 수가 없다.

따라서 q에 0을 push 해준다

그렇게 되면 이런 식으로 바뀐다.

0

7

4. 끝났는지 판별

모든 트럭들이 q를 거쳐 pop 이 되었다면 answer를 리턴한다.

그렇지 않다면 2~3의 과정을 반복하면서 answer++ 를 해준다. 여기서 answer은 수행 시간을 의미한다. 

 

bridge queue의 변화

수행시간	tail	head
0	0	0
1	7	0
2	0	7
3	4	0
4	5	4
5	0	5
6	6	0
7	0	6
8	0	0

 

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

using namespace std;


int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int car_idx = 0;
    int cur_weight = 0;
    int cur_cnt = 0;
    int passed = 0;
    queue <int> q;
    
    for(int i=0; i<bridge_length; i++)
        q.push(0);
    
    while(passed < truck_weights.size()) {
        answer++;
        
        int bye = q.front();
        if(bye != 0) {
            passed++;
            cur_cnt--;
            cur_weight -= bye;
        }
        q.pop();

        
        if(cur_weight+truck_weights[car_idx] <= weight && cur_cnt+1 < bridge_length) {
            // put on the bridge
            q.push(truck_weights[car_idx]);
            cur_weight += truck_weights[car_idx];
            car_idx++;
        }
        else {
            q.push(0);
        }
        
    }
    
    return answer;
}