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

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 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 함수를 완성하세요.

 

풀이 

 

오늘 풀어본 문제인 다리를 지나가는 트럭입니다. 기본적으로 Queue를 이용해서 푸는 문제라는 건 문제를 보면 바로 아실겁니다.

오늘도 여지 없이 하드 코딩을 하긴했는데 말 그대로의 코딩을 하였습니다.

 

1. 대기 트럭과 다리를 건너는 트럭 2종류를 모두 Queue 형식에 넣어주었습니다.

 

2. map과 같은 방식을 사용하여서 거리 또한 같이 재주려고 생각했으나 Queue는 순회가 불가능해서...(능력 부족) 그냥 vector를 하나 만들어서 트럭이 다리에 올라가는 순간에 vector에 추가를 해주고 매 반복문마다 1씩 더해주어 만일 그 숫자가 거리와 같아진다면 다리를 지나도록 하였습니다.

 

3. 최종적인 조건은 다리 위의 트럭과 대기하는 트럭이 없을 경우에 종료되도록 만들었습니다.

 

4. 마지막으로 실행결과에서 1의 오차가 있어서 1을 더해주었습니다. (아마 이 부분은 언제를 초를 세는 기점으로 하냐에 따라서 달라지는 것 같습니다.)

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include <string> #include <vector> #include <queue>   using namespace std;   int solution(int bridge_length, int weight, vector<int> truck_weights) {     int answer = 0;     int remain_w = weight;     vector<int> remain_l;     queue<int> on_bridge;     queue<int> trucks;     int trucks_size = truck_weights.size();       for (int i = 0; i < trucks_size; i++) {         trucks.push(truck_weights[i]);     }         while (!(on_bridge.size() == 0 && trucks.size() == 0)) {         if (trucks.size() > 0) {             if (remain_w >= trucks.front()) { //무게를 비교하고                 int temp = trucks.front(); // temp에 제일 앞 트럭을 저장                 on_bridge.push(temp); // 다리위에 트럭을 올림                 trucks.pop(); // 대기중이던 트럭을 뺌                 remain_w -= temp; // 남은 무게에서 올라간 무게를 뺌                 remain_l.push_back(0); // 다리에 차 하나가 올라갔다고 하고 0(나아간길이)를 넣음             }         }           for (int j = 0; j < remain_l.size(); j++) {             remain_l[j]++;             if (remain_l[j] == bridge_length) {                 remain_w += on_bridge.front();                 on_bridge.pop();             }         }           answer++; //시간을 올리고     }       return answer+1; } Colored by Color Scripter cs

 

초보자 입장에서는 좀 힘들었던 것 같습니다. 최근에 푼 문제들 중에 가장 긴것 같기도하고 조건이 많아서 그런것 같기도하네요.

 

결론 : Queue는 순회가 불가능하다.

 

※더 좋은 방법과 알고리즘 혹은 개선해야할 부분은 댓글로 적어주시면 감사하겠습니다.