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

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

프로그래머스

 

처음에 반복문을 i번째 트럭을 기준으로 돌렸다. 그러니까 초마다 트럭이 지나갔는지 체크하기도 어렵고 무게를 갱신시켜주기도 복잡해서 i를 초로 잡고 반복문을 돌렸다. 

풀이

i :  i초인 상태에서 i+1초가 될때를 얘기함 ex) 5초인 상태에서 6초가 될때 
queue<int> bridge : 다리위의 트럭이 있는지 여부를 저장

다리길이 4, 무게 10키로 제한, 트럭 7 4 5 6
 ex) 다리 끝 (큐 앞)  _ _ 7 4  다리 시작 (큐뒤  push하는 곳 ) : 7트럭이 다리위에서 2번 움직임
        다리 끝 (큐 앞)  4 5 0 0   다리 시작 (큐뒤  push하는 곳 ) : 4트럭이 4번 5 트럭이 3번 움직임 6 트럭은 무게 초과로 못올라온다.

1. index 번째 트럭이 올라갔을때 weight을 초과하지 않는지 다리위에 올라갈 수 있는 개수를 초과하지 않는지 체크한다.

-> 올라갈 수 없다면 큐에 0을 넣어준다. (트럭이 올라갈 수 없고 다리가 비어있는 상태)
-> 올라갈 수 있다면 큐에 트럭무게를 넣어주고 다리위의 트럭들의 총 무게 , 개수를 갱신시켜준다.

2. 큐 사이즈가 다리사이즈라면 다리 맨 앞에 트럭이 있는지 빈공간이 있는지 체크하고 큐를 pop한다.
(트럭들하고 빈공간을 1초동안 앞으로 이동)
-> 트럭이 있다면 트럭들의 총 무게 , 개수를 갱신시켜준다.

3. index  == truck_number라면 모든 트럭이 다리위에 올라간 것이므로
마지막 트럭이 다리위를 건너는 시간 + 지금까지 경과한 시간(i) + 1(i+1초 상태를 계산하기 때문에 현재는 i+1초이다.)
을 해주어 answer에 담고 반복문을 탈출한다.

 

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

queue<int>bridge;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int truck_number = truck_weights.size();
    int total_weight =0;
    int truck_cnt=0;
    int index=0;
    for(int i = 0 ;i<1000000;i++){
        
        if(bridge.size() == bridge_length){
            if(bridge.front()!=0)
            {    
                total_weight-=bridge.front();
                truck_cnt--;
            }
            bridge.pop();
                    
        }
        
        if(total_weight + truck_weights[index] > weight || truck_cnt + 1 > bridge_length ){
            bridge.push(0);
            continue;
        }
        
        bridge.push(truck_weights[index]);
        truck_cnt++;
        total_weight+=truck_weights[index++];
        if(index  == truck_number){
            answer= i + bridge_length +1;
            
            break;
        }
    }


    return answer;
}

 

다른 사람의 풀이 1

• queue에 pair로 저장해 {무게 , 이 트럭이 다리를 지날때 시각} 저장한다.

truck_move.push(make_pair(truck_weights.at(count), bridge_length + 1 + Time));

• queue의 "이 트럭이 다리를 지났을때 시각'과 현재 시간을 비교해서 같으면 현재 다리를 지난것이므로 무게와 개수 갱신

  if (truck_move.front().second == Time+1)​

 

다른 사람의 풀이 2

• queue에 트럭이 다리에 올라갈때 시간을 저장하여  "현재시간- 저장한 시각 = 다리길이 "일때 다리를 다 지나는 시각을 체크해주었다.

sec - q.front() == bridge_length

• 큐 맨앞의 트럭이 truck_weights의 몇번째 인지 인덱스를 int형에 저장하여 총 무게를 갱신해주었따.