[고득점Kit][큐] 다리를 지나는 트럭 ⭐⭐

C++로 풀이했습니다.
출처 : 프로그래머스 고득점 Kit 문제 풀이. https://programmers.co.kr/learn/challenges

[스택/큐] 다리를 지나는 트럭

난이도 ⭐⭐

❌

문제

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

내 풀이

첫번째 풀이

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

using namespace std;

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

	queue<int> ing;
	queue<int> wait;
	int sum = 0;

	for (auto & elem : truck_weights)
	{
		wait.push(elem);
	}

	while (true)
	{
		if (ing.empty() && wait.empty())
		{
		    answer++;
		    break;
		}
			

		if (ing.size() < bridge_length) 
		{
			if (!wait.empty() && (sum + wait.front() <= weight)) // 대기 큐에서 가져와서 추가함
			{
				ing.push(wait.front());
				sum += wait.front();
				wait.pop();
				answer++;  // 초 증가
			}
			else  // 합이 다리 무게를 넘기 때문에 대기 큐에서 가져와서 추가할 수는 없지만 대신 0 을 공백으로 큐에 추가했음. 큐 사이즈 늘릴라고
			{
				ing.push(0);
				answer++;  // 초 증가
			}
		}
		else  // 큐 사이즈가 다리 길이를 넘었을 때
		{
			sum -= ing.front();
			ing.pop();

			if (ing.front() == 0)  // 이제 큐에 0 만 남은 상태일 것
			{
				while(!ing.empty())  // 0 들 전부 없애고 비워주기
                    ing.pop();
			}
		}
	}

	return answer;
}

이 풀이는 결론적으로 틀렸다 ^^

• 프로그래머스의 기본 3개 테스트는 통과했지만 다른 테스트들에서 많이 틀렸다.

두번째 풀이

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

using namespace std;

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

	vector<pair<int, int>> list;
	queue<int> wait;
	int sum = 0;

	for (auto & elem : truck_weights)
	{
		wait.push(elem);
	}

	while (true)
	{        
        if (!wait.empty() && (sum + wait.front() <= weight))  // 대기 큐에서 가져와서 벡터에 추가함
        {
            list.push_back(make_pair(wait.front(), 0));
            sum +=  wait.front();
            wait.pop();
        }
        
        for (auto & elem : list)  // 현재 다리 위에 있는 트럭들의 움직인 거리 를 1 증가시켜준다.
	    {
		    elem.second++;
	    }
        
        answer++;  // 초 증가
        
        if (list[0].second == bridge_length)  // 맨 앞에 위치한, 즉 다리 위에 있은지 가장 오래된 트럭이 다리 위에서 움직인 거리가 다리 전체 길이가 다다랐을 경우
        {
            sum -= list[0].first;    
            list.erase(list.begin());  // 빼준다. 벡터에서.
        }
        
        if (list.empty() && wait.empty())
		{
		    break;
		}
	}

	return answer + 1;
}

• 현재 다리위에 있는 트럭들 Queue를 (트럭 무게, 다리 위에서 현재 움직인 거리)의 pair를 가진 Vector로 바꾸니까 맞췄다.
• 첫번째 풀이에서 while 돌면서 0 을 다 없애주는 작업이 입력 크기가 커지면 매우 오래걸려서 첫번째 풀이는 틀렸던 것 같다.

Queue에서 제일 중요한 개념 : 가장 나중에 들어온게 가장 늦게 나간다 !

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기