문제 해석
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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][] []
나만의 해석
내가 아직 문제 이해도가 낮아서 그런지 문제 자체가 이해하는데 시간이 좀 걸린다. 결국 다리라는 조건에 무게와 길이 맞게 짤라서 카운트하는 문제였다.
Python
def solution(bridge_length, weight, truck_weights):
bridge = [0]*bridge_length
print(bridge)
time =0
while bridge:
time +=1
bridge.pop(0)
if truck_weights:
if truck_weights[0]+ sum(bridge) <= weight:
bridge.append(truck_weights.pop(0))
else:
bridge.append(0)
return time쉽게 풀려면 정말 쉽게 풀수 있는 문제다. 사실 queue를 이용해서 어떻게 해볼려고 했는데 너무 시간소모가 많아서 단순 리스트로 진행했다. 처음에 다리를 주어진 길이만큼 만들어주고 순회하면서 문제 과정을 실제로 구현해서 카운트 해주었다. 이것보다 더 좋은 방법이 분명 있을거 같은데 ...
C++
#include <string>
#include <vector>
#include <deque>
using namespace std;
int summa(deque<int> bridge){
int sum = 0;
while(bridge.size()){
sum += bridge.front();
bridge.pop_front();
}
return sum;
}
int solution(int bridge_length, int weight, vector<int> truck_weights) {
deque<int> bridge(bridge_length);
int time =0;
while(bridge.size()){
time ++;
bridge.pop_front();
if(truck_weights.size()){
if(truck_weights.front() + summa(bridge) <= weight){
bridge.push_back(truck_weights.front());
truck_weights.erase(truck_weights.begin());
}
else{
bridge.push_back(0);
}
}
}
return time;
}CPP 너어는 진짜... 처음부터 다 구현... 우선 기본 로직은 비슷하게 가져가는데 sum()같은 함수는 만들어 줘야한다.
