[프로그래머스 LV2] 다리를 지나는 트럭 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/42583?language=cpp#

프로그래머스

 

이번에도 시뮬레이션 문제로 그림을 통해 시뮬레이션을 직접 진행해보는 것이 문제에 가장 도움이 된다. 

 

 

이렇게 표를 만들어보았다. 그리고 이름처럼 ready에 있는 트럭들은 레디큐, work에 있는 즉 다리에 있는 트럭들은 워크큐로 명명했다. 

 

먼저 시간을 신경쓰지말고 시뮬레이션을 진행해본다고 하자. 그렇다면 총 세가지 케이스가 있다.

 

1. 도로에 트럭을 올릴 수 있음 

2. 도로가 가득차서 트럭을 올릴 수 없음

3. 무게 초과로 트럭을 올릴 수 없음

 

1번: 그냥 트럭을 올리면 된다. 레디큐에서 pop하고 워크큐에 삽입한다.

2번: 도로가 가득찼다면 워크큐에서 pop한다.

3번: 무게가 초과되었으니 워크큐에서 pop한다. 

 

그리고 여기서 시간을 고려한다면 워크큐에서 하나가 나오는 순간 레디큐에서 바로 삽입이 된다. 그러므로 워크큐에서 삽입이 되는 경우에만 시간을 ++ 하도록한다.

 

또한 무게초과 때문에 삽입할 수 없을 경우 

 

만약 워크큐의 최대 크기가 10인데 4, 5, 2 인데 초과라고 하자. 그러면 맨 앞의 4를 내보낼 때 크기 - 현재 사이즈를 해주는 이런 식으로 풀어야하는데 실수할 여지도 많고 일관성을 해친다. 그래서 

 

 

파란색 0을 넣어서 레디큐에서 들어오지 않았지만 임시로 0을 넣어서 코드의 일관성을 지켰다. 이러면 확실히 속도는 느려질 수 있으나 1만 * 1만 = 1억으로 충분히 처리가능하다.

 

그리고 모든 시간을 워크큐에 푸쉬되는 순간에 만 +1 되도록한다. 

 

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    
    queue<int> readyQ;
    queue<int> workQ;
    
    for(int tw : truck_weights){
        readyQ.push(tw);
    }
    int total = 0;
    while(!readyQ.empty()){        
        int now = readyQ.front();
        
        if(workQ.empty()){
            total += now;
            readyQ.pop();
            answer++;
            workQ.push(now); continue;
        }
        if(workQ.size() == bridge_length){ // 모두 올라가있음
            total -= workQ.front();
            workQ.pop();
        }else if(total + now > weight){ // 너무 많음
            answer++;
            workQ.push(0);
        }else{ // 모두 올라가있지 않고 너무 많지 않음 들어갈 수 있음
            workQ.push(now);
            answer++;
            total += now;
            readyQ.pop();
        }
        
        
    }
    answer += bridge_length;
    
    return answer;
}