프로그래머스 스택/큐 다리를 지나는 트럭

문제 설명

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

---

제한 조건

• 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을 사용한다면 truck_weights를 스택에 넣고

현재 다리의 weight를 b_weight라는 변수로 만들어 저장해 둡니다.

stack에서 트럭을 하나씩 빼는 것을 다리에 트럭이 진입한 것이라고 볼 수 있습니다.

트럭이 진입하고 1초 뒤에 다음 트럭이 진입할 수 있게 됩니다.

첫번째 트럭을 스택에서 빼내고 +1초를 해줍니다. 동시에 첫번쨰 트럭의 시간에서 -1을 해줍니다.

(만약 트럭의 시간이 0이되면 b_weight에서 해당 트럭의 무게를 뺍니다.)

그리고 다음 트럭의 weight를 보고 다리에 올라올 무게가 weight보다 크지 않으면 트럭을 하나 더 올립니다.

이렇게 트럭이 모두 없어질 때까지 반복하면 됩니다.

 

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int count = 0;
    int i=0;
    int tmp_weight = weight;
    vector<int> t_time;
    stack<int> s1;
    for(int i=truck_weights.size()-1;i>=0;i--){
    	s1.push(truck_weights[i]);
    	t_time.push_back(bridge_length);
	}
    do{
        if(!s1.empty() &&((tmp_weight - s1.top()) >= 0)){
    		tmp_weight -= s1.top();
    		s1.pop();  
            count++;
		}
		answer++;
        for(int k=0;k<count;k++){
    	    t_time[i+k]--;
        }
    	if(t_time[i]==0){
    		tmp_weight += truck_weights[i];
    		i++;
            count--;
    	}
        
    }
    while(count != 0 || i < truck_weights.size());
    answer++;
    return answer;
}

 

 

나의 점수는 1054(+6)점이었다.

 

---

또 다른 풀이 해석 : 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0; 

    int tot_w = 0; //다리의 총 무게

    int t_front = 0; //다리위에 있는 버스 중 가장 먼저 들어간 버스
    int t_cur = 0; //다리위에 있는 버스 중 가장 마지막에 다리로 들어간 버스 id

    int sec = 0; //소요된 시간

    queue <int> q; //버스가 다리에 진입하는 시간을 담을 queue

    while (t_front != truck_weights.size()) {//모든 트럭이 다 빠져나온 경우
        if (!q.empty() && (sec - q.front() == bridge_length)) { //첫번째 버스가 다리를 빠져나오는가?
            tot_w -= truck_weights[t_front]; //다리의 무게에서 빠져나오는 버스의 무게를 제외함
            ++t_front; 
            q.pop();
        }
        if (t_cur != truck_weights.size() && tot_w + truck_weights[t_cur] <= weight) {//다리에 아직 여유공간이 있을 경우
            tot_w += truck_weights[t_cur];
            ++t_cur;
            q.push(sec);
        }
        ++sec;
    }

    answer = sec;

    return answer;
}

반성 : 나는 다리 위에 있는 모든 버스의 시간을 고려했는데 그럴 필요가 없었다는 것을 깨닳았다.

마지막에 남은 버스가 빠져나오는 시간을 구하기만 하는 문제였다는 것을 문제를 다 푼 후에야 깨닳은 것이다.

앞으로 문제 유형을 많이 보다보면 이는 해결될 것이라고 생각한다.

앞으로도 열심히 코딩테스트 문제를 풀어봐야겠다.