C++ / 프로그래머스 / 다리를 지나는 트럭

문제

 

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

프로그래머스

문제풀이

 

테스트케이스 4번 6번만 계속 틀려서 고생 좀 했다.

질문글을 보니 새 트럭이 다리에 들어간 시간이 이미 있던 트럭이 나가는 시간보다 빠르면 안 된다고 적혀있었다.

내 코드와는 관련이 없을 거라 생각하고 그냥 넘겼는데 다른 질문글로는 해결이 안 돼서 다시 보고 조건을 하나 추가했더니 맞혔다.

 

        //if (prev_time == time) ++time; 4, 6번 틀림
        if (prev_time >= time) time = prev_time + 1; // 맞힘

이 차이인데 이전시간이랑 같을 수는 있는데 이전시간이 더 큰 경우 때문에 생긴 문제였다.

 

time은 처음 차가 들어가는 시간만 1초가 걸리므로 1로 설정한다.

문제에서 bridge_length는 다리에 한 번에 올라갈 수 있는 최대 트럭수 겸 다리의 길이이다.

max_cnt나 br_len나 똑같은 값이긴 한데 편의상 변수를 따로 두어 구분했다.

weight은 다리에 올라간 트럭들의 총 무게이다.

front_truck은 큐를 하나 덜 쓰기 위해서 다리의 맨 앞에 있는 트럭을 가리키는 인덱스 값이다.

prev_time은 바로 이전 트럭이 다리에 올라간 시간 변수이다.

마지막으로  in_time은 다리에 올라간 트럭의 시간을 저장하는 큐이다.

 

    for (int idx = 0; idx < trucks.size(); ++idx) {
        while (truck_cnt >= max_cnt || weight + trucks[idx] > max_weight) {
            time = in_time.front() + br_len;
            in_time.pop();
            weight -= trucks[front_truck++];
            --truck_cnt;
        }

다리에는 트럭의 개수 제한과 무게 제한이 있다.

따라서 이번 트럭이 들어가기 전에 개수 제한이 걸리거나 이번 트럭의 무게를 더했을 때 무게 제한이 걸리는 경우 반복문을 실행한다.

현재 시간을 맨 앞 트럭의 들어간 시간+ 다리를 건너는 시간값으로 변경한다.

in_time.pop을 하여 트럭을 한대 다리에서 내보낸다.

마찬가지로 다리의 트럭들의 총무게도 빼고, 트럭의 총개수도 뺀다.

 

        if (prev_time >= time) time = prev_time + 1;
        if (idx + 1 == trucks.size()) return time + br_len;
        in_time.push(time);
        ++truck_cnt;
        weight += trucks[idx];
        prev_time = time;

반복문이 종료됐으면 현재 트럭이 올라갈 수 있다.

만약 time이 이전에 올라간 시간이하이면 이전 시간+1을 해준다.

 

만약 현재 트럭이 마지막 트럭이라면, 다리에서 마지막 트럭이 내려간 시간은 현재 time + 다리를 건너는 시간이므로 바로 해당 값을 return 하여 종료시키면 된다.

 

그 외의 경우는 트럭이 들어간 시간을 in_time에 저장하고, 트럭 개수와 무게를 더하고 이전 차량 진입 시간을 바꾸면 된다.

 

코드

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

int solution(int br_len, int max_weight, vector<int> trucks) {
    int max_cnt(br_len), truck_cnt(0), weight(0), front_truck(0);
    int time(1), prev_time(0);
    queue<int>in_time;

    for (int idx = 0; idx < trucks.size(); ++idx) {
        while (truck_cnt >= max_cnt || weight + trucks[idx] > max_weight) {
            time = in_time.front() + br_len;
            in_time.pop();
            weight -= trucks[front_truck++];
            --truck_cnt;
        }
        if (prev_time >= time) time = prev_time + 1;
        if (idx + 1 == trucks.size()) return time + br_len;
        in_time.push(time);
        ++truck_cnt;
        weight += trucks[idx];
        prev_time = time;
    }
}