[프로그래머스] 다리를 지나는 트럭

문제 설명

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

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]

---

큐를 이용한 문제이다. 

생각해보다 어려워서 풀이를 보고 풀었다.

큐에 트럭을 어떻게 넣을지를 잘 생각 못 한 것 같다.

 

큐에는 현재 다리위에 있는 트럭의 무게를 넣는다.

다리 위의 총 무게를 기록하는 변수와 트럭의 인덱스를 기록하는 변수를 선언한다.

 

0번 트럭부터 차례대로 넣으면서 트럭을 더 올릴 수 있으면 추가하고 

못한다면 0을 넣는다. 앞에 있는 트럭을 하나씩 미는 과정인데 이 생각을 못 해서 못 푼 것 같다.

마지막 트럭을 조사할때 다리의 길이만큼 추가해서 반환하면 된다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Programmers/%EB%8B%A4%EB%A6%AC%EB%A5%BC%20%EC%A7%80%EB%82%98%EB%8A%94%20%ED%8A%B8%EB%9F%AD.cpp

chosh95/STUDY

C++ 코드

#include <string>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int solution(int len, int weight, vector<int> truck) {
	int answer = 0; //시간
	int curWeight = 0; //현재 다리 위에 있는 트럭 무게
	int idx = 0; //트럭 인덱스
	queue<int> q; //다리 위에 있는 트럭 list
	while (1) {
		answer++;
		if (q.size() == len) { //트럭이 도착하면 무게 빼주고 제거
			curWeight -= q.front();
			q.pop();
		}
		if (curWeight + truck[idx] <= weight) { //트럭 추가할 수 있으면 추가
			if (idx == truck.size() - 1) { //마지막 트럭인 경우 
				answer += len;
				break;
			}
			q.push(truck[idx]);
			curWeight += truck[idx];
			idx++;
		}
		else {
			q.push(0); //트럭을 더 못 올리면 0으로 트럭 밀어주기
		}
	}
	return answer;
}

int main()
{
	cout << solution(2, 10, { 7,4,5,6 });
}