프로그래머스 [스택/큐 / 다리를 지나는 트럭](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 다리를 지나는 트럭

---

문제 링크: 문제 보기

문제 설명:

다리 길이(bl)와 견딜 수 있는 최대 무게(weight)가 주어질 때, 주어진 트럭들이 순서대로 다리를 건너는 데 걸리는 최소 시간을 구하는 문제입니다. 다리 위에는 한 번에 정해진 개수와 무게 제한 내에서만 트럭이 올라갈 수 있습니다.

---

문제 해결 코드

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

using namespace std;

int solution(int bl, int weight, vector<int> tw) {
    int answer = 0;
    int curW = 0; // 현재 다리 위의 총 무게
    queue<int> q; // 다리를 건너는 트럭을 관리하는 큐
    int i = 0; // 현재 트럭 인덱스
    
    while (true) {
        if (q.size() == bl) { // 다리 길이만큼 채워졌다면 맨 앞 트럭 제거
            curW -= q.front();
            q.pop();
        }
        
        if (i < tw.size() && curW + tw[i] <= weight) { // 새로운 트럭이 올라갈 수 있는 경우
            curW += tw[i];
            q.push(tw[i]);
            i++;
        } else { // 새로운 트럭이 못 올라가는 경우, 다리 위를 유지하기 위해 0 추가
            q.push(0);
        }
        
        answer++;
        if (i == tw.size() && curW == 0) break; // 모든 트럭이 지나가고 다리 위가 비었을 때 종료
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 큐를 이용하여 다리 위 트럭의 상태를 관리하며, 트럭이 이동하는 과정을 시뮬레이션합니다.
• 구현 세부사항:
• 큐의 크기는 다리 길이(bl)를 유지하며, 다리를 건너는 트럭을 관리합니다.
• 트럭이 다리에 진입할 수 있는지 무게 제한을 확인한 후 큐에 추가합니다.
• 진입할 수 없으면 0을 추가하여 트럭이 이동하는 효과를 만듭니다.
• 모든 트럭이 지나간 후에도 다리에서 나오는 시간을 고려해야 하므로 종료 조건을 설정합니다.
• 시간 복잡도 분석:
• 트럭 개수를 n이라고 할 때, 트럭마다 다리 길이만큼 이동해야 하므로 O(n + bl)입니다.

---

결과

이 코드는 큐를 이용하여 트럭이 다리를 건너는 과정을 효율적으로 시뮬레이션하며, 최소 시간을 계산합니다.

다른 접근 방식으로는 deque를 활용해 다리 위의 트럭을 효과적으로 관리하는 방법이 있으며, 이는 특정 경우에서 성능을 더 최적화할 수 있습니다.