다리를 지나는 트럭 문제풀이(C++, 스택/큐)[프로그래머스]

안녕하세요 멍청한 토끼입니다.

이번 문제는 프로그래머스의 스택/큐 Lv2에 해당하는

다리를 지나는 트럭 문제 입니다.

포스팅을 시작하겠습니다.

 

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

https://programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

4. 결과

---

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

---

1. 문제 설명

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

문제!!

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

---

2. 문제풀이

먼저 다리에 들어간 트럭이 다리를 먼저나오니까 선입선출의 자료구조인 큐를 이용하여 이번 문제를 풀도록 하겠습니다. 하나씩 풀어서 생각해보도록 하겠습니다. 1. 대기하는 차량이 1대 이상 존재하고, 차가 도로위에 올라갈 수 있다면 도로에 진입시킨다. 2. 대기하는 차량이 있지만 도로에 차가 올라갈 수 없다면 차량이 나갈때까지 시간을 보낸다. 3. 도로에 올라가있는 차량은 시간이 지날수록 남은 거리가 줄어든다. 4. 대기하는 차량이 없어도 도로에 차가있다면 시간을 계속 체크해야 한다. 5. 대기차도 없고 도로에 올라간 차량도 없다면 반복문 종료 ------------------------------------------------------------------------------------------------------- 그렇다면 우리가 체크해야 할것들이 있습니다. 1. 지금까지 경과한 시간 -> answer 2. 현재 도로에 올라가져있는 차 무게-> currentWeight 3. 도로에 올라가져있는 차량 리스트(큐) -> count 4. 도로에 올라가져있는 차마다 남은 거리(큐) -> brigeOn ※ 변수명읜 제가 임의로 지은것입니다. 편하신대로 바꾸셔도 무방합니다. ----------------------------------------------------------------------------------------------------- 1. 처음에는 도로에 진입한 차량중 남은 거리가 있는지 체크해야합니다. 이 순서가 뒤로가면 차량이 나가는순간 차가 들어와야 하는데 그게 1초씩 뒤로 미루어 집니다. ※ 제가 이거때문에 조금 삽질을 했습니다. 차가 도로 밖으로 나간다면 현재 도로에 올라가져있는 차량과 무게를 제외합니다. 거리가 남아있다면 1칸 전진 후 다시 리스트(큐)에 넣어줍니다. 2. 두번째로 대기차량이 있나 확인한 후 대기차량이 있다면 3. 세번째로 도로가 무게를 견딜 수 있는지 현재 도로에 올라가져있는 차량무게와 대기중인 차량무게를 더하여 비교합니다. 도로에 올라갈 수 없다면 패스합니다. 도로에 올라갈 수 있다면 도로에 올라가져있는 차량 리스트(큐)에 차량을 추가하고 현재 도로에 가중되고 있는 무게를 현재 차량만큼 추가합니다. 남은거리 리스트(큐)에 도로의 거리만큼 추가를 하고 대기차량 중 제일앞에 차량을 삭제합니다. 4. 네번째로 대기중인 차량과 도로에 올라가져있는 차량이 없다면 반복문 종료후 값을 반환합니다.

 

 

 

---

3. 소스코드

 

3.1 주석없는 코드

#include <vector>
#include <queue>
 
using namespace std;
 
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, currentWeight = 0;
    queue<int> count, bridgeOn;
    while (true) {
        int size = bridgeOn.size();
        for (int i = 0; i < size; i++){
            int length = bridgeOn.front();
            bridgeOn.pop();
            if (length <= 1) {
                currentWeight -= count.front();
                count.pop();
                continue;
            }
            bridgeOn.push(length - 1);
        }
        if (truck_weights.size() > 0 && currentWeight + truck_weights.at(0) <= weight) {
            count.push(truck_weights.at(0));
            currentWeight += truck_weights.at(0);
            bridgeOn.push(bridge_length);
            truck_weights.erase(truck_weights.begin());
        }
        answer++;
        if (truck_weights.size() == 0 && count.size() == 0)
            break;
    }
    return answer;
}

3.2 주석있는 코드

#include <vector>
#include <queue>
 
using namespace std;
 
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    //현재 도로에 올라가져있는 차 무게
    int answer = 0, currentWeight = 0;
    //도로에 올라가져있는차, 차마다 남은 거리
    queue<int> count, bridgeOn;
    while (true) {
        //중간에 차가 빠져나가면 계산이 바뀌기때문에 size고정
        int size = bridgeOn.size();
        for (int i = 0; i < size; i++){
            int length = bridgeOn.front();
            bridgeOn.pop();
            //도로 남은길이가 없다면
            if (length <= 1) {
                //도로에서 현재차 무게를 제외
                currentWeight -= count.front();
                //도로에 올라가져 있는차 제외
                count.pop();
                continue;
            }
            //남아있다면 길이감소후 다시넣기
            bridgeOn.push(length - 1);
        }
        //대기차가 1대이상 있고 도로가 무게를 견딜 수 있다면
        if (truck_weights.size() > 0 && currentWeight + truck_weights.at(0) <= weight) {
            //도로에 올라가져있는 차 추가
            count.push(truck_weights.at(0));
            //현재 올라가져있는 무게 추가
            currentWeight += truck_weights.at(0);
            //남은 도로거리 추가
            bridgeOn.push(bridge_length);
            //대기차량 삭제
            truck_weights.erase(truck_weights.begin());
        }
        //시간초 증가
        answer++;
        //도로에 올라가져있는차와 대기차가 모두없다면 반복문 탈출
        if (truck_weights.size() == 0 && count.size() == 0)
            break;
    }
    return answer;
}

3.3 테스트 코드 추가

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    //현재 도로에 올라가져있는 차 무게
    int answer = 0, currentWeight = 0;
    //도로에 올라가져있는차, 차마다 남은 거리
    queue<int> count, bridgeOn;
    while (true) {
        //중간에 차가 빠져나가면 계산이 바뀌기때문에 size고정
        int size = bridgeOn.size();
        for (int i = 0; i < size; i++){
            int length = bridgeOn.front();
            bridgeOn.pop();
            //도로 남은길이가 없다면
            if (length <= 1) {
                //도로에서 현재차 무게를 제외
                currentWeight -= count.front();
                //도로에 올라가져 있는차 제외
                count.pop();
                continue;
            }
            //남아있다면 길이감소후 다시넣기
            bridgeOn.push(length - 1);
        }
        //대기차가 1대이상 있고 도로가 무게를 견딜 수 있다면
        if (truck_weights.size() > 0 && currentWeight + truck_weights.at(0) <= weight) {
            //도로에 올라가져있는 차 추가
            count.push(truck_weights.at(0));
            //현재 올라가져있는 무게 추가
            currentWeight += truck_weights.at(0);
            //남은 도로거리 추가
            bridgeOn.push(bridge_length);
            //대기차량 삭제
            truck_weights.erase(truck_weights.begin());
        }
        //시간초 증가
        answer++;
        //도로에 올라가져있는차와 대기차가 모두없다면 반복문 탈출
        if (truck_weights.size() == 0 && count.size() == 0)
            break;
    }
    return answer;
}
 
void print(int bridge_length, int weight, vector<int> truck_weights, int answer){
    int t = solution(bridge_length, weight, truck_weights);
    cout << t << " , ";
    if (t == answer)
        cout << "정답" << endl;
    else
        cout << "틀림" << endl;
}
 
int main() {
    print(100, 100, { 10,10,10,10,10,10,10,10,10,10 }, 110);
    print(2, 10, { 7,4,5,6 }, 8);
    print(100, 100, { 10 }, 101);
 
    return 0;
}