들어가는 말
다리의 길이, 최대 무게, 지나갈 트럭의 무게가 주어진다. 이때 주어진 트럭의 순서대로 다리를 지날 수 있는 최단 시간을 구하시오.
처음에는 굉장히 쉽다고 생각했는데, 그 이유는 다리를 지나는 트럭을 큐에다가 넣어서 구하면 끝이라고 생각했다. 현재 무게라는 변수에다가 다음 트럭의 무게를 더해서 최대 무게보다 작으면 큐에다가 넣어주고 아니면 놔두고 이런 식으로. 그러나 문제가 생겼으니. 바로 시간이었다. 모든 트럭이 지나가는 시간을 구해야 하는데 도저히 위의 방식으로는 구할 수 없는 거 아닌가.
다른 이들의 풀이를 찾아보니 q에다가 0을 더하는 방식으로 시간을 구하더라. 만일 트럭이 들어올 수 있으면 트럭을 넣어주고 트럭이 들어올 수 없으면 0을 넣어줘서 트럭이 지나가는 길(시간)을 표시하는 거다. 때문에 q의 사이즈가 다리 길이의 사이즈와 같게 되면 한 트럭이 다리를 지나갔다는 게 된다.
프로그레머스 문제를 풀면서 느끼는 건데 언제나 문제를 크게 보지 못하는 거 같다. 먼저 큰 틀을 잡고 시작해야 하는데, 작은 것을 먼저 헤결하려고 하니 자꾸만 문제의 의도에서 엇나가는 느낌. 기억하자. 먼저 큰 틀을 짜는 것.
코드 설명
while(1)문으로 돌려주는데, 현재 지목하는 트럭의 인덱스가 truck_weights.size()와 같다면 break를 해준다. 왜냐하면 모든 트럭의 인덱스를 거쳤다는 의미이니까. 이때 그냥 break를 해주면 안되고 answer에다가 bridge_length를 더해줘야 한다. 왜냐하면 마지막 트럭이 지나간 시간 또한 포함해줘야 하기 때문이다.
answer에다가 ++를 해줘서 while문이 한 번 돌아갈 때마다 시간을 잰다. 그리고 현재 지목하고 있는 트럭의 무게를 tmp에 넣어준다.
만일 q의 사이즈가 다리의 길이와 같다면 이는 한 트럭이 다리를 빠져나갔다는 의미다. 그러므로 총 무게에다가 현재 빠져나간 트럭의 무게를 빼주고(q,front()) q에는 현재 빠져나간 트럭을 지워준다. 여기서 front와 pop의 주체가 단순히 트럭이라고 생각해서는 안된다. 트럭의 무게 때문에 추가된 0도 포함되는 거다.
만일 현재 무게에다가 현재 지목된 트럭의 무게를 더했을 때 총 무게보다 작다면 트럭이 지나갈 수 있다는 것이다. 그렇기에 지목된 트럭의 무게를 q에 넣어주고 weight를 더해준다. 그리고 인덱스를 다음 트럭에 넘긴다. 만일 총 무게보다 크다면 0을 넣어서 시간을 재야 한다.
코드
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0;
int tmp = 0;
int idx = 0;
int c_weight = 0;
queue<int> q;
while(1){
/*idx가 truck_weights의 크기를 가리키면 모든 트럭이 다리를 건넌 거다.*/
if(idx == truck_weights.size()){
answer = answer + bridge_length;
break;
}
answer++;
tmp = truck_weights[idx];
/*q 사이즈가 bridge_length와 같다면 한 트럭이 다리를 지는 거다.*/
if(q.size() == bridge_length){
c_weight = c_weight - q.front();
q.pop();
}
/*현재 weight와 현재 지목한 트럭 값이 weight보다 작다면 다리에 한 트럭을 추가, 아니라면 0을 추가.*/
if(c_weight + tmp <= weight){
q.push(tmp);
c_weight = c_weight + tmp;
idx++;
}else{
q.push(0);
}
}
return answer;
}