다리를 지나는 트럭
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다.
모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다.
다리에는 트럭이 최대 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 |
Python 코드
# 시간 초과 코드
def solution(bridge_length, weight, truck_weights):
answer = 0
bridge = [0] * bridge_length # 다리 위의 리스트를 선언
while len(bridge):
answer += 1 # 1초씩 증가
bridge.pop(0) # 다리 왼쪽 끝의 트럭을 pop
if truck_weights: # 대기하는 트럭이 있다면
bridge.append(truck_weights.pop(0)) # 다리에 트럭 추가
else:
bridge.append(0) # 무게가 아니라면 다리에 아무도 가지 않는다.
return answer
* 참고 링크 1 : https://par3k.tistory.com/224
from collections import deque
def solution(bridge_length, weight, truck_weights):
truck_weights = deque(truck_weights) # truck_weights(대기트럭)을 담을 deque 생성
bridge = deque([0 for _ in range(bridge_length)]) # 다리 길이만큼 0을 채워서 변수 생성 // 다리를 건너는 트럭
time = 0 # 경과 시간
bridge_weight = 0 # 지금 다리 위의 무게 // 현재 다리를 건너고 있는 무게
while len(bridge) != 0:
out = bridge.popleft() # 다리를 건너는 첫번째 트럭(bridge[0])를 pop 해줌
bridge_weight -= out # 다리 무게에서 다리를 건넌 트럭의 무게를 빼줌
time += 1 # 시간을 더해줌
if truck_weights: # deque에 요소가 남아 있으면 True
# 현재 다리를 건너는 트럭의 무게와 다리에 오를 트럭의 무게의 합이
if bridge_weight + truck_weights[0] <= weight:
# 다리가 견딜 수 있는 무게 이하일 때
left = truck_weights.popleft() # 대기트럭 deque에서 다음 트럭을 pop하고
bridge_weight += left # 다리를 건너고 있는 트럭 무게에 더하고
bridge.append(left) # 건너는 트럭 리스트에 넣어준다.
else:
# 다리가 견딜 수 있는 무게 초과일 때
bridge.append(0) # 다음 트럭이 지나가지 못하므로 0을 채워준다.
return time* 참고 링크 2 : https://coblin.xyz/29
* 그림 설명 참고 링크 : https://eunhee-programming.tistory.com/149
* 참고 링크 3 : https://latte-is-horse.tistory.com/130
* 유튜브 설명 링크 : https://www.youtube.com/watch?v=Y9HYe4cUiZM&t=388s
* deque
- 양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너
- 양방향 큐
- 데이터의 회전도 가능
- maxlen을 설정하여 최대 항목 수를 설정
* 참고 링크 4 : https://www.youtube.com/watch?v=05roQ6gFwsM
C++ 코드
#include <queue>
#include <vector>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0;
int idx=0; //차량 지목용 idx
int sum=0; //현재 다리에 올라와있는 차량 무게 총합
queue<int> q; //현재 다리를 건너는 트럭 체크용 큐
while(1){
if(idx == truck_weights.size()){ //마지막 트럭일 때
answer += bridge_length; //마지막 트럭이 지나는 시간 추가
break;
}
answer++; //시간초 증가
int tmp = truck_weights[idx];
//차가 다리를 다 건넜을 경우
if(q.size() == bridge_length){
sum -= q.front(); //다 건넜으니 현재 다리에 있는 차들의 무게에서 제외
q.pop();
}
if(sum + tmp <= weight){ //다리에 다음 차가 진입할 수 있다면
sum += tmp; //차량 무게 추가
q.push(tmp);
idx++; //다음 차량을 위해서
}else{
q.push(0); //진입할 수 없다면 0을 푸시해서 시간초 계산
}
}
return answer;
}
출처
'코딩테스트 > Programmers' 카테고리의 다른 글
| [코딩테스트/Programmers] 23_주식가격 (Lv2.) (0) | 2022.01.18 |
|---|---|
| [코딩테스트/Programmers] 22_기능개발 (Lv2.) (0) | 2022.01.17 |
| [코딩테스트/Programmers] 20_정수 제곱근 판별 (Lv1.) (0) | 2022.01.11 |
| [코딩테스트/Programmers] 19_최대공약수와 최소공배수 (Lv1.) (0) | 2022.01.11 |
| [코딩테스트/Programmers] 18_자릿수 더하기 (Lv1.) (0) | 2022.01.11 |
