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

프로그래머스

[문제 설명]

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

 

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 

[제한 조건]

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

[입출력 예]

bridge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

---

[문제 풀이]

문제를 이해하는것은 어렵지 않았지만 푸는데 오랜 시간이 걸렸다.

트럭을 큐에 넣고 빼는 타이밍때문인지 계속 틀렸다고 나와서 디버깅하는데 시간이 오래걸린것 같다.

자료구조 유형 문제여서 stack이나 queue를 사용하는 문제들이지만, deque라는 양방향 큐에 대해 알게되어 사용했다.

아직 완전하게 알지 못하지만, 사용 가능한 함수를 봤을때는 stack + queue 인 것 같다. 양쪽으로 다 넣고 빼고가 가능해서 자주 사용하게 될 것 같다. deque의 정체와 사용법에 대해서는 따로 블로그 글을 작성해야겠다.

 

내 생각에 이 문제에서 주의해야할 점은 예제의 2초에서 3초로 넘어갈때이다.

3초가 되면 다리에 있던 무게가 7인 트럭이 나오면서 동시에 대기 트럭에 있던 4가 다리위로 올라온다.

이것을 봤을때 다리 위에 있는 트럭이 조건에 맞으면 먼저 빼주고, 그 후 다음 트럭이 올라올 수 있는 조건인지 체크해서 올려야 한다.

 

우선 deque에 첫번째 트럭을 넣어준다. 이때 트럭의 무게와 들어간 시점의 시간을 저장하고 다리에 올라간 트럭의 총 무게도 따로 변수에 저장해둔다.

 

deque에 첫번째 트럭을 넣고 나서, while문에서 시간을 1씩 증가시킨다.

먼저 트럭을 빼주기 위해서 조건을 체크해야 하는데..

deque의 맨 처음에 저장된 트럭이 진입한 시간을 현재 시간에서 빼주었을때 다리의 길이와 같으면 그 트럭은 다리를 다 지나온 것으로 판단 할 수 있다. (트럭은 1초에 1씩 움직인다.)

 

위 예제에서 첫번째 트럭이 1초에 다리에 진입했고, 3초일때 다리에서 빠져나가므로

현재시간(3초) - 트럭 진입시간(1초) == 다리길이(2) 일때가 트럭이 빠져나올 조건이다.

 

이후에 트럭을 올려줄 조건을 체크하면 된다.

 

현재 다리에 올라간 트럭의 총 무게와 현재 맨앞에 대기하고 있는 트럭의 무게가 제한 무게를 넘지 않으면 deque에 대기 트럭중 제일 앞 트럭의 무게와 현재 시간을 저장한다.

 

위의 과정을 계속 진행하다가 수행 시간을 줄이기 위해 마지막 트럭일때 현재 시간에 다리 길이만큼 더해주게되면

마지막 트럭까지 나간 시간과 같다고 볼 수 있다.

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <string>
#include <vector>
#include <deque>
#include <utility>
#include <iostream>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 1;
    deque<pair<int,int>> dq;
    int truck_num = truck_weights.size();
    int index = 0;
    dq.push_back({truck_weights[index++],answer});
    int totalWeights = truck_weights[0];
    while(!dq.empty() && index < truck_num)
    {
        answer++;
        if((answer - dq.front().second) >= bridge_length)
        {
            totalWeights -= dq.front().first;
            dq.pop_front();
        }

        if(totalWeights + truck_weights[index] <= weight)
        {
            totalWeights += truck_weights[index];
            dq.push_back({truck_weights[index++],answer});
        }
    }
    answer += bridge_length;
    return answer;
    
}